tek4

Các Phép Toán Trong TRPO và PPO – Học Tăng Cường

by - September. 21, 2021
Kiến thức
<p><img class="aligncenter wp-image-6573 size-full" src="../../../wp-content/uploads/2020/12/a-1.jpg" alt="" width="1000" height="664" /></p> <p style="text-align: center;">Ảnh chụp bởi&nbsp;<a href="https://unsplash.com/@crissyjarvis">Crissy Jarvis</a></p> <p>Trong c&aacute;c b&agrave;i trước, ch&uacute;ng ta đ&atilde; n&oacute;i qua về cơ bản c&aacute;c c&ocirc;ng thức, một số phương ph&aacute;p v&agrave; c&aacute;c giải thuật cơ bản trong TRPO v&agrave; PPO. C&aacute;c bạn c&oacute; thể kham thảo qua c&aacute;c b&agrave;i viết trước để nắm được cơ bản về 2 phương ph&aacute;p n&agrave;y. Phương ph&aacute;p TRPO v&agrave; PPO đều dựa tr&ecirc;n thuật to&aacute;n MM &nbsp;Minorize-Maximization.&nbsp;Lần n&agrave;y, ch&uacute;ng ta sẽ tr&igrave;nh b&agrave;y chi tiết về c&aacute;c ph&eacute;p to&aacute;n trong TRPO v&agrave; PPO hơn đằng sau c&aacute;c h&agrave;m mục ti&ecirc;u. Đồng thời, ch&uacute;ng ta sẽ đề cập đến c&aacute;c kh&aacute;i niệm cơ bản về thuật to&aacute;n MM v&agrave; đi qua c&aacute;c bước về c&aacute;ch tối ưu h&agrave;m mục ti&ecirc;u cho TRPO v&agrave; PPO.</p> <h1>H&agrave;m thay thế</h1> <p>RL tối đa h&oacute;a phần thưởng khấu hao kỳ vọng. Đường cong m&agrave;u đỏ b&ecirc;n dưới thể hiện phần thưởng khấu hao kỳ vọng &eta; được định nghĩa như sau:</p> <p>[latexpage]\[\eta (\pi _{\theta})=E_{\tau \sim \pi_{\theta}}\left [ \sum _{t=0}^{\infty}\gamma ^{t}r_{t} \right ]\]</p> <p><img class="aligncenter wp-image-6564 size-full" src="../../../wp-content/uploads/2020/12/a-4.jpeg" alt="phep-toan-trong-TRPO-va-PPO" width="1000" height="352" /></p> <p style="text-align: center;"><a href="https://drive.google.com/file/d/0BxXI_RttTZAhMVhsNk5VSXU0U3c/view">Nguồn</a></p> <p>Thuật to&aacute;n MM l&agrave; một phương ph&aacute;p thực hiện v&ograve;ng lặp. Với mỗi v&ograve;ng lặp, ch&uacute;ng ta sẽ t&igrave;m được một h&agrave;m thay thế M (đường cong m&agrave;u xanh lam).</p> <ul> <li>L&agrave; một h&agrave;m giới hạn dưới cho &eta;.</li> <li>T&iacute;nh xấp xỉ &eta; với chiến thuật hiện tại</li> <li>Dễ d&agrave;ng tối ưu h&oacute;a (ch&uacute;ng ta sẽ t&iacute;nh gần đ&uacute;ng h&agrave;m thay thế dưới dạng phương tr&igrave;nh bậc hai).</li> </ul> <p>Trong mỗi v&ograve;ng lặp, ch&uacute;ng ta t&igrave;m điểm tối ưu cho M v&agrave; sử dụng điểm đ&oacute; l&agrave;m chiến thuật hiện tại.</p> <p><img class="aligncenter wp-image-6565 size-full" src="../../../wp-content/uploads/2020/12/a-5.jpeg" alt="phep-toan-trong-TRPO-va-PPO" width="1000" height="352" /></p> <p style="text-align: center;"><a href="https://jonathan-hui.medium.com/rl-the-math-behind-trpo-ppo-d12f6c745f33">Nguồn</a></p> <p>Sau đ&oacute;, ch&uacute;ng ta đ&aacute;nh gi&aacute; lại giới hạn dưới của chiến thuật mới v&agrave; lặp lại v&ograve;ng lặp. Khi ch&uacute;ng ta tiếp tục qu&aacute; tr&igrave;nh n&agrave;y, chiến thuật sẽ tiếp tục được cải thiện. V&igrave; chỉ c&oacute; một chiến thuật c&oacute; t&iacute;nh khả thi, do đ&oacute;, chiến thuật hiện tại sẽ hội tụ v&agrave; tối ưu h&oacute;a tại điểm cục bộ hoặc to&agrave;n cục.</p> <p><img class="aligncenter wp-image-6566 size-full" src="../../../wp-content/uploads/2020/12/a-6.jpeg" alt="phep-toan-trong-TRPO-va-PPO" width="1000" height="237" /></p> <p style="text-align: center;"><a href="https://drive.google.com/file/d/0BxXI_RttTZAhMVhsNk5VSXU0U3c/view">Nguồn</a></p> <h1>H&agrave;m mục ti&ecirc;u</h1> <p>Như đ&atilde; n&oacute;i, Natural Policy Gradient, TRPO, v&agrave; PPO bắt đầu thực hiện với h&agrave;m mục ti&ecirc;u sau đ&acirc;y. Ch&uacute;ng ta sẽ chứng minh chi tiết hơn trong phần tiếp theo.</p> <p>[latexpage]\[maximize _{\theta}\;\;\widehat{E}_{t}\left [ \frac{\pi _{\theta}(a_{t|}s_{t})}{\pi _{\theta _{old}}(a_{t}|s_{t})}\widehat{A}_{t} \right ]\]</p> <p>Với điều kiện l&agrave;&nbsp;[latexpage]$\widehat{E}_{t}[KL[\pi _{\theta _{old}}(\cdot |s_{t}),\pi _{\theta}(\cdot |s_{t})]]\leq \delta$</p> <p>Hoặc</p> <p>[latexpage]\[maximize _{\theta}\;\; \widehat{E}_{t}\left [ \frac{\pi _{\theta}(a_{t|}s_{t})}{\pi _{\theta _{old}}(a_{t}|s_{t})}\widehat{A}_{t} \right ] - \beta\widehat{E}_{t}[KL[\pi _{\theta _{old}}(\cdot |s_{t}),\pi _{\theta}(\cdot |s_{t})]]\]</p> <p>T&oacute;m lại, ch&uacute;ng ta muốn tối đa h&oacute;a h&agrave;m lợi &iacute;ch: phần thưởng kỳ vọng trừ đi điểm tối thiểu (Baseline) để l&agrave;m giảm phương sai. Nhưng ch&uacute;ng ta sẽ &aacute;p dụng một r&agrave;ng buộc với chiến thuật mới sao cho kh&ocirc;ng được qu&aacute; ch&ecirc;nh lệch so với chiến thuật cũ. Phần c&ograve;n lại của b&agrave;i viết n&agrave;y sẽ giải th&iacute;ch về r&agrave;ng buộc n&agrave;y sử dụng to&aacute;n học.</p> <h2>K&yacute; hiệu cho c&aacute;c h&agrave;m gi&aacute; trị, gi&aacute; trị h&agrave;nh động v&agrave; c&aacute;c h&agrave;m lợi &iacute;ch</h2> <p>Trước ti&ecirc;n, ta sẽ định nghĩa h&agrave;m gi&aacute; trị Q, h&agrave;m gi&aacute; trị v&agrave; h&agrave;m lợi &iacute;ch.</p> <p>[latexpage]\[Q_{\pi}(s_{t},a_{t})=E_{s_{t+1},a_{t+1},...}\left [ \sum _{l=0}^{\infty}\gamma ^{l}r(s_{t+1}) \right ]\]</p> <p>[latexpage]\[V_{\pi}(s_{t})=E_{a_{t},s_{t+1},...}\left [ \sum _{l=0}^{\infty}\gamma ^{l}r(s_{t+1}) \right ]\]</p> <p>[latexpage]\[A_{\pi}(s,a)=Q_{\pi}(s,a)-V_{\pi}(s)\]</p> <p>[latexpage]\[a_{t}\sim \pi(a_{t}|s_{t}),s_{t+1}\sim P(s_{t+1}|s_{t},a_{t})\]</p> <p>[latexpage]\[t \geq 0\]</p> <h2>Phần thưởng khấu hao kỳ vọng</h2> <p>Phần thưởng khấu hao kỳ vọng &eta; được t&iacute;nh như sau:</p> <p>[latexpage]\[\eta (\pi)=E_{s_{0},a_{0},...}\left [ \sum_{t=0}^{\infty}\gamma ^{t}r(s_{t}) \right ]\]</p> <p>Trong đ&oacute; [latexpage]$s_{0}\sim p_{0}(s_{0}),a_{t}\sim \pi(a_{t}|s_{t}),s_{t+1}\sim P(s_{t+1}|s_{t},a_{t})$</p> <p>Ngo&agrave;i ra, ch&uacute;ng ta c&oacute; thể t&iacute;nh to&aacute;n phần thưởng của một chiến thuật bằng c&aacute;ch sử dụng một chiến thuật kh&aacute;c. Điều n&agrave;y tạo ra cơ sở cho việc so s&aacute;nh hai chiến thuật.</p> <p>[latexpage]\[\eta (\widetilde{\pi})=\eta(\pi)+\sum _{s}P_{\widetilde{\pi}}(s)\sum_{a}\widetilde{\pi}(a|s)A_{\pi}(s,a)\]</p> <p>Trong đ&oacute; [latexpage]$p_{\pi}$ l&agrave; tần số thăm d&ograve; bị khấu hao (chưa được chuẩn h&oacute;a) v&agrave; [latexpage]$s_{0}\sim p_{0}$</p> <p>[latexpage]\[p_{\pi}(s)=P(s_{0}=s)+\gamma P(s_{1}=s)+\gamma ^{2}P(s_{2}=2)+...\]</p> <p>Chứng minh như sau:</p> <p>[latexpage]$E_{r\sim \pi '}\left [ \sum_{t=0}^{\infty}\gamma ^{t}A^{\pi}(s_{t},a_{t}) \right ]=E_{\tau \sim \pi '}\left [ \sum _{t=0}^{\infty}\gamma ^{t+1}V^{\pi}(s_{t+1})-\sum _{t=0}^{\infty}\gamma ^{t}V^{\pi}(s_{t}) \right ]$</p> <p>[latexpage]$=\eta(\pi ')+ E_{\tau \sim \pi '}\left [ \sum_{t=0}^{\infty}\gamma ^{t+1}V^{\pi}(s_{t+1})-\sum_{t=0}^{\infty}\gamma ^{t}V^{\pi}(s_{t}) \right ]$<br />[latexpage]$=\eta(\pi ')+ E_{\tau \sim \pi '}\left [ \sum _{t=1}^{\infty}\gamma ^{t}V^{\pi}(s_{t})-\sum_{t=0}^{\infty}\gamma^{t}V^{\pi}(s_{t}) \right ]$<br />[latexpage]$=\eta(\pi ')-E_{\tau \sim \pi '}[V^{\pi}(s_{0})]=\eta(\pi ')-\eta (\pi)$</p> <h1>H&agrave;m 𝓛</h1> <p>Tiếp theo, để sử dụng thuật to&aacute;n MM, ch&uacute;ng ta sẽ t&igrave;m h&agrave;m giới hạn dưới m&agrave; t&iacute;nh xấp xỉ &eta; cục bộ với chiến thuật hiện tại. H&agrave;m [latexpage]$\mathcal{L}$ được định nghĩa như sau:</p> <p>[latexpage]\[L_{\pi}(\widetilde{\pi})=\eta(\pi)+\sum_{s}p_{\pi}(s)\sum_{a}\widetilde{\pi}(a|s)A_{\pi}(s,a)\]</p> <p>Như đ&atilde; đề cập trước đ&oacute;, [latexpage]$\mathcal{L}$ l&agrave; một phần của h&agrave;m giới hạn dưới M (được gạch dưới m&agrave;u đỏ b&ecirc;n dưới).</p> <p><img class="aligncenter wp-image-6567 size-full" src="../../../wp-content/uploads/2020/12/a-7.jpeg" alt="phep-toan-trong-TRPO-va-PPO" width="1000" height="245" /></p> <p style="text-align: center;"><a href="https://jonathan-hui.medium.com/rl-the-math-behind-trpo-ppo-d12f6c745f33">Nguồn</a></p> <p>Số hạng thứ hai nằm trong h&agrave;m M ch&iacute;nh l&agrave; KL-Divergence:</p> <p>[latexpage]\[D_{KL}(P||Q)=E_{x}log\frac{P(x)}{Q(x)}\]</p> <p>Với chiến thuật hiện tại, n&oacute; tương đương với [latexpage]$KL(\theta_{i},\theta_{i})$, c&oacute; gi&aacute; trị l&agrave; 0. Hệ số C nh&acirc;n với KL c&oacute; thể được xem như l&agrave; sai số giới hạn tr&ecirc;n của L.</p> <p>Với chiến thuật hiện tại [latexpage]$\theta_{i}$, ch&uacute;ng ta c&oacute; thể biểu diễn L triển khai hệ số &eta; bằng với biểu thức bậc nhất.</p> <p>[latexpage]\[L_{\pi_{\theta _{i}}}(\pi_{\theta _{i}})=\eta(\pi _{\theta_{i}})\]</p> <p>[latexpage]\[\triangledown _{\theta}L_{\pi_{\theta_{i}}}(\pi_{\theta})|_{\theta=\theta_{i}}=\triangledown _{\theta}\eta(\pi_{\theta})|_{\theta=\theta_{i}}\]</p> <p>V&igrave; [latexpage]$KL(\theta_{i},\theta_{i})=0$, M t&iacute;nh xấp xỉ cục bộ phần thưởng kỳ vọng. Tiếp theo, ch&uacute;ng ta sẽ tr&igrave;nh b&agrave;y chi tiết về h&agrave;m giới hạn dưới M. Một đoạn chứng minh trong phụ lục của b&agrave;i b&aacute;o TRPO thiết lập h&agrave;m giới hạn dưới cho &eta; như sau.</p> <p>[latexpage]\[\eta (\pi _{new})\geq L_{\pi_{old}}(\pi_{new})-\frac{4\epsilon \gamma}{(1-\gamma)^{2}}\alpha ^{2}\]<br />[latexpage]\[\epsilon = max_{s,a}\;|A_{\pi}(s,a)|\]<br />[latexpage]\[\alpha=D_{TV}^{max}(\pi_{old},\pi_{new})\]<br />[latexpage]\[D_{TV}^{max}(\pi,\widetilde{\pi})=max\;D_{TV}(\pi(\cdot |s)||\widetilde{\pi}(\cdot |s))\]<br />[latexpage]\[D_{TV}(p||q)=\frac{1}{2}\sum_{i}|p_{i}-q_{i}|\]</p> <p>D_TV, tổng ph&acirc;n kỳ cho phương sai, v&igrave;</p> <p>[latexpage]\[D_{TV}(p||q)^{2}\leq D_{KL}(p||q)\]</p> <p>N&ecirc;n ch&uacute;ng ta sẽ thay thế D_TV bằng KL-Divergence</p> <p>Ch&uacute;ng ta viết lại h&agrave;m giới hạn dưới như sau:</p> <p>[latexpage]\[\eta(\widetilde{\pi})\geq L_{\pi}(\widetilde{\pi})-CD_{KL}^{max}(\pi,\widetilde{\pi})\]</p> <p>Trong đ&oacute;&nbsp;[latexpage]$C=\frac{4\epsilon \gamma}{(1-\gamma)^{2}}$ v&agrave; [latexpage]$D_{KL}^{max}(\pi,\widetilde{\pi})=max_{s}D_{KL}(\pi(\cdot |s)||\widetilde{\pi}(\cdot |s))$</p> <p>Lưu &yacute;: Ch&uacute;ng ta sẽ đơn giản h&oacute;a k&yacute; hiệu sử dụng</p> <p>[latexpage]\[\eta(\theta):=\eta(\pi_{\theta})\]<br />[latexpage]\[L_{\theta}(\widetilde{\theta}):=L_{\pi_{\theta}}(\pi_{\widetilde{\theta}})\]</p> <h1>Đảm bảo t&iacute;nh tăng đơn điệu</h1> <p>Kh&aacute;i niệm ch&iacute;nh của Natural Policy Gradient l&agrave; đảm bảo t&iacute;nh tăng đơn điệu. T&oacute;m lại, về mặt l&yacute; thuyết, n&oacute; sẽ đảm bảo mỗi lần cập nhật cho chiến thuật mới sẽ tốt hơn so với chiến thuật cũ. Điều ch&uacute;ng ta thực sự muốn chứng minh ở đ&acirc;y l&agrave; chiến thuật mới được tạo ra từ việc tối ưu h&oacute;a M sẽ đảm bảo rằng n&oacute; sẽ hoạt động tốt hơn trong &eta; (phần thưởng kỳ vọng thực tế) so với chiến thuật cũ. V&igrave; chỉ c&oacute; hữu hạn c&aacute;c chiến thuật, n&ecirc;n việc cải tiến li&ecirc;n tục sẽ chỉ đưa ch&uacute;ng ta đến một điểm tối ưu cục bộ hoặc to&agrave;n cục. Ta sẽ chứng minh như sau:</p> <p>Bất kỳ sự cải thiện n&agrave;o trong [latexpage]$M_{i}(\pi_{i+1})$ so với [latexpage]$M(\pi_{i})$ đều sẽ đẩy [latexpage]$\eta(\pi_{i+1})$ l&ecirc;n một lượng gi&aacute; trị tương tự</p> <p>Với [latexpage]$M_{i}(\pi)=L_{\pi_{i}}(\pi)-CD_{KL}^{max}(\pi_{i},\pi)$, sau đ&oacute; ta t&iacute;nh: [latexpage]$\eta(\pi_{i+1})\geq M_{i}(\pi_{i+1})$</p> <p>V&igrave; [latexpage]$\eta(\pi_{i})=M_{i}(\pi_{i})$, do vậy [latexpage]$\eta(\pi_{i+1})-\eta(\pi_{i})\geq M_{i}(\pi_{i+1})-M(\pi_{i})$</p> <h1>V&ograve;ng lặp chiến thuật với Sự đảm bảo t&iacute;nh tăng đơn điệu</h1> <p>Sau đ&acirc;y l&agrave; thuật to&aacute;n lặp lại đảm bảo rằng chiến thuật mới sẽ lu&ocirc;n hoạt động tốt hơn chiến thuật hiện tại.</p> <p><em>Thuật to&aacute;n:</em></p> <ul> <li>Khởi tạo [latexpage]$\pi_{0}$</li> <li>V&ograve;ng lặp từ i=0,1,2,... cho tới khi hội tụ, thực hiện <ul> <li>T&iacute;nh to&aacute;n c&aacute;c gi&aacute; trị lợi &iacute;ch [latexpage]$A_{\pi_{i}}(s,a)$</li> <li>Giải b&agrave;i to&aacute;n tối ưu c&oacute; r&agrave;ng buộc</li> <li>[latexpage]$\pi_{i+1}=argmax_{\pi}\;[L_{\pi_{i}}(\pi)-CD_{KL}^{max}(\pi_{i},\pi)]$</li> </ul> </li> </ul> <p>Trong đ&oacute;: [latexpage]$C=4\epsilon\gamma /(1-\gamma)^{2}$ v&agrave; [latexpage]$L_{\pi_{i}}(\pi)=\eta(\pi_{i})+\sum_{s}p_{\pi_{i}}(s)\sum_{a}\pi(a|s)A_{\pi_{i}}(s,a)$</p> <p>Tuy nhi&ecirc;n, việc t&igrave;m ra gi&aacute; trị lớn nhất của KL Divergence (trong số tất cả c&aacute;c chiến thuật) l&agrave; điều rất kh&oacute;. Thay v&agrave;o đ&oacute;, ch&uacute;ng ta sẽ nới lỏng y&ecirc;u cầu v&agrave; sử dụng gi&aacute; trị trung b&igrave;nh của KL Divergence.</p> <p>[latexpage]\[maximize_{\theta}L_{\theta_{old}}(\theta)\]<br />với điều kiện [latexpage]$D_{KL}^{max}(\theta_{old},\theta)\leq \delta$</p> <p>Chuyển sang dạng như sau:<br />[latexpage]\[maximize_{\theta}\;L_{\theta_{old}}(\theta)\]<br />với điều kiện [latexpage]$\overline{D}_{KL}^{p_{\theta_{old}}}(\theta_{old},\theta)\leq \delta$<br />[latexpage]\[\overline{D}_{KL}^{p}(\theta_{1},\theta_{2}):=E_{s\sim p}[D_{KL}(\pi_{\theta_{1}}(\cdot |s)||\pi_{\theta_{2}}(\cdot |s))]\]</p> <p>𝓛 được định nghĩa như sau:</p> <p>[latexpage]\[L_{\pi}(\widetilde{\pi})=\eta(\pi)+\sum_{s}p_{\pi}(s)\sum_{a}\widetilde{\pi}(a|s)A_{\pi}(s,a)\]</p> <p>Ch&uacute;ng ta c&oacute; thể sử dụng Importance Sampling để t&iacute;nh L.H.S. bằng c&aacute;ch lấy mẫu từ chiến thuật q:</p> <p>[latexpage]\[\sum_{a}\pi_{\theta}(a|s_{n})A_{\theta_{old}}(s_{n},a)=E_{a\sim q}\left [ \frac{\pi_{\theta}(a|s_{n})}{q(a|s_{n})}A_{\theta_{old}}(s_{n},a) \right ]\]</p> <p>H&agrave;m mục ti&ecirc;u được viết lại như sau:</p> <p>[latexpage]\[maximize_{\theta}\;\;E_{s\sim p_{\theta_{old}},a\sim q}\left [ \frac{\pi_{\theta}(a|s)}{q(a|s)}\widehat{A}_{\theta_{old}}(s,a) \right ]\]</p> <p>Với điều kiện&nbsp;[latexpage]$E_{s\sim p_{\theta_{old}}}[D_{KL}(\pi_{\theta_{old}}(\cdot |s)||\pi_{\theta}(\cdot |s))]\leq \delta$</p> <p>Với t&iacute;nh đối ngẫu Lagrangian, một r&agrave;ng buộc cho h&agrave;m mục ti&ecirc;u c&oacute; thể được kết hợp ngược trở lại cho h&agrave;m mục ti&ecirc;u với một cấp số nh&acirc;n. Cả hai l&agrave; đều giống nhau về mặt to&aacute;n học:</p> <p>[latexpage]\[maximize _{\theta}\;\;\widehat{E}_{t}\left [ \frac{\pi _{\theta}(a_{t|}s_{t})}{\pi _{\theta _{old}}(a_{t}|s_{t})}\widehat{A}_{t} \right ]\]</p> <p>Với điều kiện l&agrave;&nbsp;[latexpage]$\widehat{E}_{t}[KL[\pi _{\theta _{old}}(\cdot |s_{t}),\pi _{\theta}(\cdot |s_{t})]]\leq \delta$</p> <p>Hoặc</p> <p>[latexpage]\[maximize _{\theta}\;\; \widehat{E}_{t}\left [ \frac{\pi _{\theta}(a_{t|}s_{t})}{\pi _{\theta _{old}}(a_{t}|s_{t})}\widehat{A}_{t} \right ] - \beta\widehat{E}_{t}[KL[\pi _{\theta _{old}}(\cdot |s_{t}),\pi _{\theta}(\cdot |s_{t})]]\]</p> <p>Trong Gradient Ascent, ch&uacute;ng ta sẽ x&aacute;c định hướng c&oacute; độ dốc cao nhất v&agrave; sau đ&oacute; thực hiện bước tiếp theo hướng đ&oacute;. Tuy nhi&ecirc;n, nếu tỷ lệ học tập qu&aacute; cao, h&agrave;nh động c&oacute; thể đi chệch khỏi h&agrave;m phần thưởng thực tế qu&aacute; nhiều.</p> <p><img class="aligncenter wp-image-6568 size-full" src="../../../wp-content/uploads/2020/12/a-8.jpeg" alt="phep-toan-trong-TRPO-va-PPO" width="1000" height="504" /></p> <p style="text-align: center;"><a href="https://pronetowanderfriends.wordpress.com/2014/02/23/angels-landing-in-zion-national-park-check/">Nguồn</a></p> <p>Trong v&ugrave;ng tin cậy, ch&uacute;ng ta giới hạn t&igrave;m kiếm của m&igrave;nh trong một v&ugrave;ng do \delta kiểm so&aacute;t. Về mặt to&aacute;n học, ch&uacute;ng ta chứng minh trong phần trước rằng khu vực như vậy th&igrave; sẽ đảm bảo được chiến thuật tối ưu của n&oacute; sẽ hoạt động tốt hơn chiến thuật hiện tại cho đến khi n&oacute; đạt đến mức tối ưu cục bộ hoặc to&agrave;n cục.</p> <p><img class="aligncenter wp-image-6569 size-full" src="../../../wp-content/uploads/2020/12/a-9.jpeg" alt="phep-toan-trong-TRPO-va-PPO" width="1000" height="644" /></p> <p style="text-align: center;"><a href="https://jonathan-hui.medium.com/rl-the-math-behind-trpo-ppo-d12f6c745f33">Nguồn</a></p> <p>Khi ch&uacute;ng ta tiếp tục thực hiện v&ograve;ng lặp, ta sẽ đạt được đến điểm tối ưu.</p> <h1>Tối ưu h&oacute;a h&agrave;m mục ti&ecirc;u</h1> <p>Như ch&uacute;ng ta đ&atilde; đề cập trước đ&acirc;y, h&agrave;m giới hạn dưới M sẽ dễ d&agrave;ng để tối ưu h&oacute;a. Tr&ecirc;n thực tế, ch&uacute;ng ta t&iacute;nh xấp xỉ L v&agrave; gi&aacute; trị trung b&igrave;nh của KL-Divergence bằng c&aacute;ch sử dụng Chuỗi Taylor với bậc một cho L v&agrave; bậc hai cho KL-Divergence:</p> <p>[latexpage]\[\mathcal{L}_{\theta _{k}}(\theta)\approx g^{T}(\theta -\theta _{k})\]</p> <p>[latexpage]\[g\doteq \triangledown _{\theta}\mathcal{L}_{\theta _{k}}(\theta)|_{\theta _{k}}\]</p> <p>[latexpage]\[\overline{D}_{KL}(\theta||\theta _{k})\approx\frac{1}{2}(\theta -\theta _{k})^{T}H(\theta - \theta _{k})\]</p> <p>[latexpage]\[H\doteq \triangledown _{\theta}^{2}\overline{D}_{KL}(\theta|\theta _{k})|_{\theta _{k}}\]</p> <p>Trong đ&oacute; g l&agrave; Policy Gradient v&agrave; H được l&agrave; ma trận th&ocirc;ng tin Fisher FIM ở dạng ma trận Hessian.</p> <p>[latexpage]\[H=\triangledown ^{2}f=\begin{pmatrix}\frac{\partial ^{2}f_{1}}{\partial x_{1}^{2}} &amp;\frac{\partial ^{2}f_{1}}{\partial x_{1}\partial x_{2}}&amp;...&amp;\frac{\partial^{2}f_{1}}{\partial x_{1} \partial x_{n}}\\ \frac{\partial ^{2}f_{2}}{\partial x_{1}^{2}} &amp; \frac{\partial ^{2}f_{2}}{\partial x_{1}\partial x_{2}}&amp;...&amp;\frac{\partial^{2}f_{2}}{\partial x_{1} \partial x_{n}} \\ \vdots &amp;\vdots &amp;\ddots &amp;\vdots \\ \frac{\partial ^{2}f_{m}}{\partial x_{1}^{2}} &amp;\frac{\partial ^{2}f_{m}}{\partial x_{1}\partial x_{2}}&amp;..&amp;\frac{\partial^{2}f_{m}}{\partial x_{1}\partial x_{n}}\end{pmatrix}\]</p> <p>B&agrave;i to&aacute;n tối ưu sẽ c&oacute; dạng như sau:</p> <p>[latexpage]\[\theta_{k+1}=armax_{\theta}\;\;g^{T}(\theta - \theta_{k})\]<br />[latexpage]\[s.t.\;\;\frac{1}{2}(\theta - \theta_{k})^{T}H(\theta - \theta_{k})\leq\delta\]</p> <p>Ch&uacute;ng ta c&oacute; thể giải n&oacute; bằng c&aacute;ch tối ưu h&oacute;a một phương tr&igrave;nh bậc hai v&agrave; nghiệm của n&oacute; sẽ c&oacute; dạng:</p> <p>[latexpage]\[\theta_{k+1}=\theta_{k}+\sqrt{\frac{2\delta}{g^{T}H^{-1}g}}H^{-1}g\]</p> <p>Ph&eacute;p t&iacute;nh ở tr&ecirc;n được gọi l&agrave; Natural Policy Gradient. Đ&acirc;y l&agrave; thuật to&aacute;n tối ưu h&oacute;a chiến thuật bằng c&aacute;ch sử dụng thuật to&aacute;n MM v&agrave; Natural Policy Gradient.</p> <p><em>Giải thuật cho Natural Policy Gradient:</em></p> <ul> <li>Đầu v&agrave;o: c&aacute;c tham số chiến thuật ban đầu l&agrave; [latexpage]$\theta_{0}$</li> <li>V&ograve;ng lặp k=0,1,2... thực hiện <ul> <li>Thu thập tập dữ liệu [latexpage]$\mathcal{D}_{k}$ dựa tr&ecirc;n chiến thuật [latexpage]$\pi_{k}=\pi(\theta_{k})$</li> <li>T&iacute;nh c&aacute;c gi&aacute; trị lợi &iacute;ch [latexpage]$\widehat{A}_{t}^{\pi_{k}}$ sử dụng giải thuật t&iacute;nh to&aacute;n gi&aacute; trị lợi &iacute;ch</li> <li>Tạo lập c&aacute;c ph&eacute;p t&iacute;nh mẫu cho</li> <li>Policy Gradient [latexpage]$\widehat{g}_{k}$ (sử dụng ph&eacute;p t&iacute;nh gi&aacute; trị lợi &iacute;ch)</li> <li>Ma trận KL-Divergence Hessian hoặc ma trận th&ocirc;ng tin [latexpage]$\widehat{H}_{k}$</li> <li>Thực hiện cập nhật cho Natural Policy Gradient</li> </ul> </li> </ul> <p>[latexpage]\[\theta_{k+1}=\theta_{k}+\sqrt{\frac{2\delta}{\widehat{g}^{T}_{k}\widehat{H}_{k}^{-1}\widehat{g}_{k}}}\widehat{H}^{-1}_{k}\widehat{g}_{k}\]</p> <ul> <li>Kết th&uacute;c v&ograve;ng lặp</li> </ul> <h1>TRPO</h1> <p>Tuy nhi&ecirc;n, FIM (H) v&agrave; ma trận nghịch đảo của n&oacute; sẽ rất tốn k&eacute;m cho việc t&iacute;nh to&aacute;n. TRPO sẽ t&iacute;nh hệ số sau:</p> <p>[latexpage]\[H^{-1}g\]</p> <p>Bằng c&aacute;ch t&igrave;m x cho phương tr&igrave;nh bậc một như sau:</p> <p>[latexpage]\[x_{k}\approx \widehat{H}_{k}^{-1}\widehat{g}_{k}\]</p> <p>[latexpage]\[\widehat{H}_{k}x_{k}\approx \widehat{g}\]</p> <p>Ch&uacute;ng ta c&oacute; thể giải n&oacute; bằng phương ph&aacute;p Gradient li&ecirc;n hợp &iacute;t phức tạp hơn l&agrave; t&igrave;m ma trận nghịch đảo của H. Gradient li&ecirc;n hợp tương tự như Gradient Descent nhưng n&oacute; c&oacute; thể t&igrave;m được điểm tối ưu trong nhiều nhất N v&ograve;ng lặp, trong đ&oacute; N l&agrave; số lượng tham số c&oacute; trong m&ocirc; h&igrave;nh.</p> <p><img class="aligncenter wp-image-6570 size-full" src="../../../wp-content/uploads/2020/12/a-1.png" alt="" width="1050" height="358" /></p> <p style="text-align: center;"><a href="https://jonathan-hui.medium.com/rl-the-math-behind-trpo-ppo-d12f6c745f33">Nguồn</a></p> <p><em>Giải thuật như sau:</em></p> <ul> <li>Đầu v&agrave;o: c&aacute;c tham số chiến thuật ban đầu l&agrave; [latexpage]$\theta_{0}$</li> <li>V&ograve;ng lặp k=0,1,2... thực hiện <ul> <li>Thu thập tập dữ liệu [latexpage]$\mathcal{D}_{k}$ dựa tr&ecirc;n chiến thuật [latexpage]$\pi_{k}=\pi(\theta_{k})$</li> <li>T&iacute;nh c&aacute;c gi&aacute; trị lợi &iacute;ch [latexpage]$\widehat{A}_{t}^{\pi_{k}}$ sử dụng giải thuật t&iacute;nh to&aacute;n gi&aacute; trị lợi &iacute;ch</li> <li>Tạo lập c&aacute;c ph&eacute;p t&iacute;nh mẫu cho</li> <li>Policy Gradient [latexpage]$\widehat{g}_{k}$ (sử dụng ph&eacute;p t&iacute;nh gi&aacute; trị lợi &iacute;ch)</li> <li>H&agrave;m t&iacute;ch giữa v&eacute;c tơ Hessian v&agrave; KL-Divergence [latexpage]$f(v)=\widehat{H}_{k}v$</li> <li>Sử dụng CG với n_{cg} v&ograve;ng lặp để t&iacute;nh được [latexpage]$x_{k}\approx\widehat{H}_{k}^{-1}\widehat{g}_{k}$</li> <li>T&iacute;nh to&aacute;n bước đi [latexpage]$\triangle _{k}\approx \sqrt{\frac{2\delta}{x_{k}^{T}\widehat{H}_{k}x_{k}}}x_{k}$</li> </ul> </li> </ul> <p>[latexpage]\[\theta_{k+1}=\theta_{k}+\triangle _{k}\]</p> <h1>PPO với mục ti&ecirc;u được lược bỏ</h1> <p style="text-align: justify;">Trong phương ph&aacute;p n&agrave;y, ch&uacute;ng ta muốn sử dụng ph&eacute;p tối ưu h&oacute;a bậc một như Gradient Descent để tối ưu h&oacute;a b&agrave;i to&aacute;n của ch&uacute;ng ta với một r&agrave;ng buộc mềm để &aacute;p đạt việc điều chỉnh cho h&agrave;m mục ti&ecirc;u nếu ch&uacute;ng ta thay đổi chiến thuật qu&aacute; nhiều.</p> <p style="text-align: justify;">Trong qu&aacute; tr&igrave;nh thực hiện, ch&uacute;ng ta duy tr&igrave; hai v&ugrave;ng mạng chiến thuật. V&ugrave;ng đầu ti&ecirc;n l&agrave; chiến thuật hiện tại m&agrave; ch&uacute;ng ta muốn điều chỉnh.</p> <p>[latexpage]\[\pi_{\theta}(a_{t}|s_{t})\]</p> <p>V&ugrave;ng mạng thứ hai l&agrave; chiến thuật m&agrave; ch&uacute;ng ta sử dụng lần cuối để thu thập c&aacute;c mẫu</p> <p>[latexpage]\[\pi_{\theta_{k}}(a_{t}|s_{t})\]</p> <p>Với &yacute; tưởng của phương ph&aacute;p Importance Sampling, ch&uacute;ng ta c&oacute; thể đ&aacute;nh gi&aacute; chiến thuật mới với c&aacute;c mẫu được thu thập từ một chiến thuật cũ hơn. Điều n&agrave;y sẽ gi&uacute;p cho việc cải thiện hiệu quả hoạt động.</p> <p>[latexpage]\[maximize_{\theta}\;\;\widehat{E}_{t}\left [ \frac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{old}}(a_{t}|s_{t})}\widehat{A}_{t} \right ]\]</p> <p>Nhưng khi ch&uacute;ng ta điều chỉnh chiến thuật hiện tại, độ ch&ecirc;nh lệch giữa chiến thuật hiện tại v&agrave; chiến thuật cũ ng&agrave;y c&agrave;ng lớn. Phương sai của ph&eacute;p t&iacute;nh sẽ tăng l&ecirc;n. V&igrave; vậy, giả sử cứ 4 v&ograve;ng lặp, ch&uacute;ng ta lại đồng bộ h&oacute;a v&ugrave;ng mạng thứ hai với chiến thuật hiện tại.</p> <p>[latexpage]\[\pi_{\theta_{k+1}}(a_{t}|s_{t})\leftarrow \pi_{\theta}(a_{t}|s_{t})\]</p> <p>Trong PPO, ch&uacute;ng ta t&iacute;nh to&aacute;n tỷ lệ giữa chiến thuật mới v&agrave; chiến thuật cũ như sau:</p> <p>[latexpage]\[r_{t}(\theta)=\pi_{\theta}(a_{t}|s_{t})/\pi_{\theta _{k}}(a_{t}|s_{t})\]</p> <p>V&agrave; ch&uacute;ng ta x&acirc;y dựng một h&agrave;m mục ti&ecirc;u mới để cắt bớt h&agrave;m lợi &iacute;ch đ&atilde; được t&iacute;nh nếu chiến thuật mới ch&ecirc;nh lệch nhiều với chiến thuật cũ. H&agrave;m mục ti&ecirc;u mới l&agrave;:</p> <p>[latexpage]\[\mathcal{L}_{\theta_{k}}^{CLIP}(\theta)=E_{\tau\sim \pi_{k}}\left [ \sum_{t=0}^{T}\left [ min(r_{t}(\theta)\widehat{A}_{t}^{\pi_{k}},clip(r_{t}(\theta),1-\epsilon,1+\epsilon)\widehat{A}_{t}^{\pi_{k}}) \right ] \right ]\]</p> <p>Nếu tỷ lệ x&aacute;c suất giữa chiến thuật mới v&agrave; chiến thuật cũ nằm ngo&agrave;i phạm vi [latexpage]$1-\epsilon$ v&agrave; [latexpage]$1+\epsilon$, h&agrave;m lợi &iacute;ch sẽ bị cắt bớt.&nbsp;[latexpage]$\epsilon$ được đặt th&agrave;nh 0,2 cho c&aacute;c th&iacute; nghiệm trong b&agrave;i b&aacute;o về PPO.</p> <p><img class="aligncenter wp-image-6571 size-full" src="../../../wp-content/uploads/2020/12/a-2.png" alt="" width="1050" height="296" /></p> <p style="text-align: center;"><a href="https://arxiv.org/pdf/1707.06347.pdf">Nguồn</a></p> <p>Điều n&agrave;y l&agrave;m giảm sự thay đổi chiến thuật qu&aacute; nhiều. Sau đ&acirc;y l&agrave; thuật to&aacute;n của giải thuật PPO với mục ti&ecirc;u được lược bỏ:</p> <ul> <li>Đầu v&agrave;o: c&aacute;c tham số chiến thuật ban đầu l&agrave; [latexpage]$\theta_{0}$, điểm ngưỡng để lược bỏ [latexpage]$\epsilon$<br />V&ograve;ng lặp k=0,1,2... thực hiện <ul> <li>Thu thập tập dữ liệu [latexpage]$\mathcal{D}_{k}$ dựa tr&ecirc;n chiến thuật [latexpage]$\pi_{k}=\pi(\theta_{k})$</li> <li>T&iacute;nh c&aacute;c gi&aacute; trị lợi &iacute;ch [latexpage]$\widehat{A}_{t}^{\pi_{k}}$ sử dụng giải thuật t&iacute;nh to&aacute;n gi&aacute; trị lợi &iacute;ch</li> <li>Cập nhật cho chiến thuật</li> </ul> </li> </ul> <p>[latexpage]\[\theta_{k+1}=argmax_{\theta}\;\;\mathcal{L}_{\theta_{k}}^{CLIP}(\theta)\]</p> <ul> <li style="list-style-type: none;"> <ul> <li>Thực hiện K bước SGD (bằng Adam), trong đ&oacute;</li> </ul> </li> </ul> <p>[latexpage]\[\mathcal{L}_{\theta_{k}}^{CLIP}(\theta)=E_{\tau\sim \pi_{k}}\left [ \sum_{t=0}^{T}\left [ min(r_{t}(\theta)\widehat{A}_{t}^{\pi_{k}},clip(r_{t}(\theta),1-\epsilon,1+\epsilon)\widehat{A}_{t}^{\pi_{k}}) \right ] \right ]\]</p> <ul> <li>Kết th&uacute;c v&ograve;ng lặp</li> </ul> <p>Đến đ&acirc;y l&agrave; kết th&uacute;c của b&agrave;i n&agrave;y. Hy vọng rằng mọi người đ&atilde; nắm được th&ecirc;m về kiến thức của TRPO v&agrave; PPO, c&ugrave;ng c&aacute;c ph&eacute;p to&aacute;n trong TRPO v&agrave; PPO. Mong mọi người sẽ tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo trong series Học tăng cường tr&ecirc;n <a href="http://tek4.vn">tek4</a> nh&eacute;!</p> <hr /> <p style="text-align: center;"><em><strong>Fanpage Facebook:</strong>&nbsp;<a href="https://www.facebook.com/tek4.vn/">TEK4.VN</a></em>&nbsp;</p> <p style="text-align: center;"><em><strong>Tham gia cộng đồng để chia sẻ, trao đổi v&agrave; thảo luận:</strong>&nbsp;<a href="https://www.facebook.com/groups/tek4.vn/">TEK4.VN - Học Lập Tr&igrave;nh Miễn Ph&iacute;</a></em></p>