TRPO v&agrave; PPO đều c&ugrave;ng dựa tr&ecirc;n thuật to&aacute;n MM (Minorize-Maximization). Trong b&agrave;i n&agrave;y, ch&uacute;ng ta sẽ c&ugrave;ng b&agrave;n về c&aacute;c chứng minh đ&atilde; được đưa ra trong c&aacute;c b&agrave;i b&aacute;o n&oacute;i về TRPO v&agrave; PPO.
<h1 style="text-align: justify;">Độ ch&ecirc;nh lệch giữa c&aacute;c phần thưởng khấu hao</h1>
Độ ch&ecirc;nh lệch giữa c&aacute;c phần thưởng khấu hao của hai chiến thuật được định nghĩa như sau:
\[J(\pi ')-J(\pi)=E_{\tau \sim \pi '}\left [ \sum _{t=0}^{\infty}\gamma ^{t}A^{\pi} (s_{t},a_{t})\right ]\]
Chứng minh:
\[E_{\tau \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}(R(s_{t},a_{t},s_{t+1})+\gamma V^{\pi}(s_{t+1})-V^{\pi}(s_{t})) \right ]\] \[=J(\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 ]\]
\[=J(\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 ]\]
\[= J(\pi ')-E_{\tau \sim \pi '}\left [ V^{\pi}(s_{0}) \right ]\]
\[=J(\pi ')-J(\pi)\]
<h1 style="text-align: justify;">Natural Policy Gradient c&oacute; t&iacute;nh tương quan</h1>
Đối với c&aacute;c gi&aacute; trị thay đổi tham số nhỏ&nbsp;$\triangle h$ v&agrave;&nbsp;$\triangle \theta$, ch&uacute;ng ta c&oacute;&nbsp;$\triangle \theta = \triangledown _{h}\theta ^{T}\triangle h$. Nếu Natural Policy Gradient l&agrave; quy tắc thay đổi c&oacute; t&iacute;nh tương quan, th&igrave; một sự thay đổi&nbsp;$\triangle h$ c&ugrave;ng với Gradient&nbsp;$\triangledown _{h}J(h)$ sẽ cho ra kết quả l&agrave; c&aacute;c thay đổi giống như vậy $\triangle \theta$ c&ugrave;ng với Gradient $\triangledown _{\theta}J(\theta)$ cho c&ugrave;ng một k&iacute;ch thước bước nhảy v&ocirc; hướng $\alpha$. Bằng c&aacute;ch t&iacute;nh đạo h&agrave;m, ch&uacute;ng ta c&oacute; thể t&iacute;nh được $\triangledown _{h}J(h)=\triangledown _{h}\theta\triangledown _{\theta}J(\theta)$. Ma trận th&ocirc;ng tin Fisher bao gồm hệ số nh&acirc;n đ&ocirc;i Jacobian $\triangledown _{h}\theta$.
\[F(h)=\int _{X}d^{\pi}(x)\int _{U}\pi (u|x)\triangledown _{h}log \pi (u|x)\triangledown _{h}log\pi(u|x)^{T}dudx,\] \[=\triangledown _{h}\theta\int _{X}d^{\pi}(x)\int _{U}\pi(u|x)\triangledown _{\theta}log \pi (u|x)\triangledown_{\theta}log\pi(u|x)^{T}dudx\triangledown_{h}\theta^{T}\] \[=\triangledown _{h}\theta F(\theta)\triangledown _{h}\theta ^{T}\]
Điều n&agrave;y chỉ ra rằng Natural Gradient trong ph&eacute;p tham số h&oacute;a h được cho bởi:
\[\widetilde{\triangledown}_{h}J(h)=F^{-1}(h)\triangledown _{h}J(h)=(\triangledown _{h}\theta F(\theta)\triangledown _{h}\theta ^{T})^{-1}\triangledown _{h}\theta\triangledown_{\theta}J(\theta)\]
Điều n&agrave;y chỉ ra rằng Natural Policy c&oacute; t&iacute;nh tương quan bởi:
\[\triangle \theta=\alpha \triangledown _{h}\theta ^{T}\triangle h=\alpha \triangledown _{h}\theta ^{T}\widetilde{\triangledown}_{h}J(h),=\alpha \triangledown _{h}\theta ^{T}(\triangledown _{h}\theta F(\theta)\triangledown _{h}\theta ^{T})^{-1}\triangledown _{h}\theta \triangledown _{\theta}J(\theta)\]
\[= \alpha F^{-1}(\theta)\triangledown _{\theta}J(\theta)=\alpha \widetilde{\triangledown}_{\theta}J(\theta)\]
Giả sử rằng $\triangledown _{h} \theta$ l&agrave; ma trận khả nghịch. Điều n&agrave;y đ&atilde; kết luận rằng Natural Policy Gradient l&agrave; một quy tắc thay đổi Gradient c&oacute; t&iacute;nh tương quan.
<h1 style="text-align: justify;">T&iacute;nh xấp xỉ độ ch&ecirc;nh lệch giữa c&aacute;c phần thưởng khấu hao với 𝓛</h1>
\[J(\pi ')\approx J(\pi)+\mathcal{L}_{\pi}(\pi ')\]
Chứng minh như sau (Giả sử 2 chiến thuật l&agrave; giống nhau):
\[J(\pi ')-J(\pi)\]=E_{\tau \sim \pi '}\left [ \sum _{t=0}^{\infty} \gamma ^{t}A^{\pi}(s_{t},a_{t}) \right ]\]
\[=\frac{1}{1-\gamma}E_{s\sim d^{\pi '}|a\sim\pi'}[A^{\pi}(s,a)]\]
\[=\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 ]\approx\frac{1}{1-\gamma}E_{s\sim d^{\pi}|a\sim\pi'}\]
\[=\mathcal{L}_{\pi}(\pi ')\]
\[J(\pi ')\approx J(\pi)+\mathcal{L}_{\pi}(\pi ')\]
<h1 style="text-align: justify;">𝓛 v&agrave; K l&agrave; bậc một</h1>
Cụ thể như sau:
\[K(\pi)=\mathcal{L}(\pi)\] \[K'(\pi)=\mathcal{L}'(\pi)\]
Chứng minh như sau:
\[K(\pi)=J(\pi ')-J(\pi)=\mathcal{L}_{\pi}(\pi)\] \[\triangledown _{\pi '}J(\pi ')-J(\pi)=\triangledown _{\pi '}J(\pi ')\]
\[\triangledown _{\pi '}J(\pi ')= E_{\tau \sim \pi}\left [ \sum _{t=0}^{\infty}\gamma ^{t}\triangledown _{\theta}log\pi _{\theta}(a_{t}|s_{t})|_{\theta _{k}}A^{\pi _{\theta _{k}}}(s_{t},a_{t}) \right ]\]
\[= E_{\tau \sim \pi}\left [ \sum _{t=0}^{\infty}\gamma ^{t}\frac{\triangledown _{\pi '}\pi (a_{t}|s_{t}|_{\pi})}{\pi (a_{t}|s_{t})}A^{\pi}(s_{t},a_{t}) \right ]\]
\[=\triangledown _{\pi '}\mathcal{L}_{\pi}(\pi ')\]
\[K'(\pi)=\triangledown _{\pi '}J(\pi ')-J(\pi)= \triangledown _{\pi '}\mathcal{L} _{\pi}(\pi ')\]
<h1 style="text-align: justify;">T&iacute;nh xấp xỉ phần thưởng kỳ vọng với phương tr&igrave;nh bậc 2</h1>
Mục ti&ecirc;u như sau:
\[\pi _{k+1}=argmax _{\pi '}\mathcal{L} _{\pi _{k}}(\pi ')\] \[s.t \;\;\overline{D}_{KL}(\pi '||\pi _{k})\leq \delta\]
Ch&uacute;ng ta c&oacute; thể sử dụng chuỗi Taylor để khai triển cả hai hệ số ở tr&ecirc;n l&ecirc;n đến bậc hai. Bậc hai của 𝓛 nhỏ hơn nhiều so với hệ số KL-divergence v&agrave; do vậy, c&aacute;c hệ số n&agrave;y sẽ coi như bằng 0, ta c&oacute; c&ocirc;ng thức như sau:
\[\mathcal{L}_{\theta _{k}}(\theta)\approx g^{T}(\theta -\theta _{k})\] \[g\doteq \triangledown _{\theta}\mathcal{L}_{\theta _{k}}(\theta)|_{\theta _{k}}\] \[\overline{D}_{KL}(\theta||\theta _{k})\approx\frac{1}{2}(\theta -\theta _{k})^{T}H(\theta - \theta _{k})\] \[H\doteq \triangledown _{\theta}^{2}\overline{D}_{KL}(\theta|\theta _{k})|_{\theta _{k}}\]
Trong đ&oacute; g l&agrave; Policy Gradient v&agrave; H đo độ nhạy của chiến thuật so với tham số m&ocirc; h&igrave;nh &theta;.
Do đ&oacute;, mục ti&ecirc;u của ch&uacute;ng ta c&oacute; thể được ước t&iacute;nh xấp xỉ như sau l&agrave;:
\[\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\]
Hoặc
\[maximize _{\theta}\;\;g^{T}(\theta -\theta _{k})-\frac{1}{2}(\theta - \theta_{k})^{T}H(\theta - \theta _{k})\]
<h1 style="text-align: justify;">H&agrave;m 𝓛 &amp; M</h1>
Ch&uacute;ng ta muốn chứng minh:
\[\mathcal{L}_{\pi}(\pi)=0\]
Trong qu&aacute; tr&igrave;nh chứng minh, ch&uacute;ng ta cũng sẽ biểu diễn M t&iacute;nh to&aacute;n xấp xỉ c&aacute;c hệ số cục bộ sau (một y&ecirc;u cầu đối với phương ph&aacute;p MM):
\[J(\pi ')-J(\pi)\]
1. Độ ch&ecirc;nh lệch giữa c&aacute;c phần thưởng khấu hao giữa hai chiến thuật kh&aacute;c nhau c&oacute; thể được t&iacute;nh l&agrave;:
\[J(\pi ')-J(\pi)=E_{\tau \sim \pi '}\left [ \sum _{t=0}^{\infty}\gamma ^{t}A^{\pi} (s_{t},a_{t})\right ]\]
2. 𝓛 c&oacute; thể được t&iacute;nh to&aacute;n xấp xỉ như sau:
\[J(\pi ')-J(\pi)\approx \mathcal{L}_{\pi}(\pi ')\]
Trong đ&oacute;,&nbsp;$J(\pi ')-J(\pi) = K(\pi ')$
3. Khi $\pi '=\pi $ th&igrave; L.H.S. ở tr&ecirc;n l&agrave; 0 v&agrave; ch&uacute;ng ta c&oacute; thể biểu diễn như sau:
\[\mathcal{L}_{\pi}(\pi)=0\]
Y&ecirc;u cầu trong điều (3) đặc biệt quan trọng. V&igrave; DL-divergence bằng 0 khi cả hai chiến thuật đều giống nhau, R.H.S. b&ecirc;n dưới sẽ t&iacute;nh gần đ&uacute;ng với h&agrave;m mục ti&ecirc;u của ch&uacute;ng ta cục bộ tại &pi; &rsquo;= &pi;. Đ&acirc;y l&agrave; một y&ecirc;u cầu đối với thuật to&aacute;n MM.
Chứng minh:
Ph&eacute;p to&aacute;n
\[J(\pi ')-J(\pi)\geq \mathcal{L}_{\pi}(\pi ')- C\sqrt{E_{s\sim d^{\pi}}[D_{KL}(\pi '||\pi)[s]]}\]
Chuyển sang dạng như sau:
\[J(\pi ')-J(\pi) = \mathcal{L}_{\pi}(\pi ')- C\sqrt{E_{s\sim d^{\pi}}[D_{KL}(\pi '||\pi)[s]]}\]
Như vậy M đ&atilde; t&iacute;nh xấp xỉ h&agrave;m mục ti&ecirc;u cục bộ.
Đế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 cơ bản về c&aacute;c chứng m&igrave;nh của TRPO v&agrave; PPO. Mọi người h&atilde;y theo d&otilde;i c&aacute;c b&agrave;i tiếp theo trong Học tăng cường c&ugrave;ng <a href="http://tek4.vn">tek4</a> nh&eacute;!
<hr />
Fanpage Facebook:&nbsp;<a href="https://www.facebook.com/tek4.vn/">TEK4.VN</a>&nbsp;
Tham gia cộng đồng để chia sẻ, trao đổi v&agrave; thảo luận:&nbsp;<a href="https://www.facebook.com/groups/tek4.vn/">TEK4.VN - Học Lập Tr&igrave;nh Miễn Ph&iacute;</a>

Admin

TRPO và PPO – Chứng Minh Toán Học – Học Tăng Cường

Cùng tác giả

Admin

Có liên quan