tek4

Học Giá Trị – Học Tăng Cường

by - September. 26, 2021
Kiến thức
<h1><img class="aligncenter wp-image-6407 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/a-5.jpg" alt="" width="1000" height="802" /></h1> <p style="text-align: center;">Ảnh chụp bởi&nbsp;<a href="https://unsplash.com/@pavement_special">Riccardo Annandale</a></p> <h1>Giới thiệu</h1> <p>Học gi&aacute; trị, hay Value Learning, l&agrave; một kh&aacute;i niệm cơ bản trong RL học tăng cường. N&oacute; l&agrave; một điểm khởi đầu để c&oacute; thể học về Học tăng cường (RL) v&agrave; c&oacute; t&iacute;nh chất cơ bản như mạng nơ-ron được li&ecirc;n kết to&agrave;n diện, tiếng anh l&agrave; Fully Connected Neural Network) trong Học s&acirc;u (Deep Learning). N&oacute; t&iacute;nh to&aacute;n v&agrave; đo lường mức độ để đạt được c&aacute;c trạng th&aacute;i (State) nhất định hoặc thực hiện một số h&agrave;nh động n&agrave;o đ&oacute; (Action). C&oacute; thể l&agrave; sẽ kh&ocirc;ng đủ nếu chỉ sử dụng phương ph&aacute;p học gi&aacute; trị để giải quyết một vấn đề phức tạp, tuy nhi&ecirc;n n&oacute; đ&oacute;ng vai tr&ograve; nền tảng ch&iacute;nh cho nhiều phương ph&aacute;p RL kh&aacute;c. Trong b&agrave;i viết n&agrave;y, ch&uacute;ng ta sẽ sử dụng c&aacute;c v&iacute; dụ để m&ocirc; tả về kh&aacute;i niệm của n&oacute;.</p> <p>Giả sử bạn lập một kế hoạch cho một chuyến đi từ SF đến SJ. Giả sử bạn l&agrave; một người rất y&ecirc;u khoa học dữ liệu v&agrave; bạn xem x&eacute;t rất nhiều yếu tố trong c&aacute;c quyết định của m&igrave;nh. Những yếu tố n&agrave;y c&oacute; thể bao gồm khoảng c&aacute;ch, t&igrave;nh trạng giao th&ocirc;ng, t&igrave;nh trạng đường x&aacute; v&agrave; thậm ch&iacute; l&agrave; cơ hội c&oacute; thể nhận được v&eacute; xe để đi. Sau khi ph&acirc;n t&iacute;ch, bạn t&iacute;nh điểm cho mỗi th&agrave;nh phố v&agrave; bạn sẽ chọn con đường đi tiếp theo m&agrave; c&oacute; điểm cao nhất.</p> <p><img class="aligncenter wp-image-6304 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-142.png" alt="Hoc-gia-tri" width="761" height="269" /></p> <p>&nbsp;</p> <p>V&iacute; dụ, khi bạn ở điểm SB, bạn c&oacute; hai tuyến đường c&oacute; thể đi. Dựa tr&ecirc;n số điểm của c&aacute;c 2 tuyến đường đ&oacute;, SM c&oacute; điểm cao hơn v&agrave; do đ&oacute;, ch&uacute;ng ta sẽ đi SM thay v&igrave; WSM.</p> <p><img class="aligncenter wp-image-6305 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-143.png" alt="Hoc-gia-tri" width="757" height="253" /></p> <p>Trong học tăng cường (RL), c&aacute;c phương ph&aacute;p học gi&aacute; trị cũng dựa tr&ecirc;n một nguy&ecirc;n tắc tương tự. Ch&uacute;ng ta sẽ t&iacute;nh to&aacute;n mức độ c&oacute; lợi cho m&igrave;nh khi ở trong một trạng th&aacute;i n&agrave;o đ&oacute;. Sau đ&oacute; ch&uacute;ng ta thực hiện c&aacute;c h&agrave;nh động cho c&aacute;c trạng th&aacute;i tiếp theo m&agrave; c&oacute; số điểm v&agrave; phần thưởng (Reward) c&oacute; gi&aacute; trị l&agrave; cao nhất.</p> <h1>H&agrave;m gi&aacute; trị</h1> <p>Về cơ bản, h&agrave;m gi&aacute; trị V(s) đo lường mức độ c&oacute; lợi khi ở trong một trạng th&aacute;i cụ thể. Theo định nghĩa th&igrave; đ&oacute; l&agrave; phần thưởng khấu hao kỳ vọng dựa theo một chiến thuật (Policy) cụ thể:</p> <p>[latexpage]\[V^{\pi}(s_{t})=\sum_{t'=t}^{T}E_{\pi_{\theta}}\left [ \gamma^{t'-t}r(s_{t'},a_{t'})|s_{t} \right ]\]</p> <p>trong đ&oacute; &gamma; l&agrave; hệ số chiết khấu. Nếu &gamma; nhỏ hơn một, ch&uacute;ng ta sẽ tiến h&agrave;nh đ&aacute;nh gi&aacute; phần thưởng trong tương lai m&agrave; c&oacute; gi&aacute; trị thấp hơn so với gi&aacute; trị hiện tại. Trong hầu hết c&aacute;c v&iacute; dụ trong phần n&agrave;y, ch&uacute;ng ta sẽ đặt gi&aacute; trị &gamma; th&agrave;nh 1 nhằm đơn giản h&oacute;a trong việc minh họa. Mục ti&ecirc;u của ch&uacute;ng ta l&agrave; t&igrave;m ra chiến thuật&nbsp;tối đa h&oacute;a phần thưởng kỳ vọng.</p> <p>[latexpage]\[V^{*}(s)=max_{\pi}E\left [ \sum_{t=0}^{H}\gamma^{t}R(s_{t},a_{t},s_{t+1})|\pi,s_{0}=s \right ]\]</p> <p>C&oacute; nhiều phương ph&aacute;p để t&igrave;m ra chiến thuật tối ưu th&ocirc;ng qua việc học gi&aacute; trị. Ch&uacute;ng ta sẽ thảo luận về ch&uacute;ng trong c&aacute;c phần tiếp theo.</p> <h1>Phương ph&aacute;p V&ograve;ng lặp gi&aacute; trị</h1> <p>Đầu ti&ecirc;n, ch&uacute;ng ta c&oacute; thể sử dụng lập tr&igrave;nh động để t&iacute;nh to&aacute;n gi&aacute; trị tối ưu của V lặp lại.</p> <p>[latexpage]\[V^{*}(s)=max_{a}E\left [ R_{t+1}+\gamma V^{*}(S_{t+1})|S_{t}=s,A_{t}=a \right ]\]</p> <p>Sau đ&oacute;, ch&uacute;ng ta c&oacute; thể sử dụng h&agrave;m gi&aacute; trị để c&oacute; được một chiến thuật tối ưu.</p> <p>Khi ch&uacute;ng ta ở SB, ch&uacute;ng ta sẽ c&oacute; hai sự lựa chọn.</p> <p><img class="aligncenter wp-image-6306 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-144.png" alt="Hoc-gia-tri" width="758" height="249" /></p> <p>Đường SB đến SM sẽ c&oacute; phần thưởng l&agrave; -10 bởi v&igrave; SM nằm ở xa hơn. Ch&uacute;ng ta sẽ nhận được th&ecirc;m phần thưởng l&agrave; &nbsp;-5 cho phần đường SB đến WSM</p> <p>Điểm tối ưu sẽ l&agrave; V * (SM) = max (-10 + V * (SM), -15 + V * (WSM)) = 60.</p> <p>V&iacute; dụ về V&ograve;ng lặp gi&aacute; trị:</p> <p>Dưới đ&acirc;y l&agrave; một m&ecirc; cung với lối ra ở tr&ecirc;n c&ugrave;ng b&ecirc;n tr&aacute;i. Tại mỗi vị tr&iacute;, sẽ c&oacute; bốn h&agrave;nh động c&oacute; thể xảy ra: l&ecirc;n, xuống, sang tr&aacute;i hoặc sang phải. Nếu ch&uacute;ng ta chạm phải đường bi&ecirc;n, ch&uacute;ng ta sẽ bị bật trở lại vị tr&iacute; ban đầu. Mỗi bước di chuyển sẽ đi được 1 bước v&agrave; nhận được phần thưởng l&agrave; gi&aacute; trị -1. Bắt đầu từ trạng th&aacute;i cuối c&ugrave;ng, ch&uacute;ng ta sẽ truyền gi&aacute; trị của V * bằng c&aacute;ch sử dụng:</p> <p>[latexpage]\[V^{*}(s)=max_{a}E\left [ R_{t+1}+\gamma V^{*}(S_{t+1})|S_{t}=s,A_{t}=a \right ]\]</p> <p>Sau đ&acirc;y l&agrave; h&igrave;nh minh họa từ v&ograve;ng lặp bắt đầu từ một đến bảy.</p> <p><img class="aligncenter wp-image-6307 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-145.png" alt="Hoc-gia-tri" width="770" height="356" /></p> <p style="text-align: center;">Được chỉnh sửa từ <a href="https://mitpress.mit.edu/books/reinforcement-learning-second-edition">nguồn</a></p> <p>Sau khi ho&agrave;n th&agrave;nh, đối với mỗi vị tr&iacute;, ch&uacute;ng ta sẽ x&aacute;c định c&aacute;c vị tr&iacute; xung quanh m&agrave; c&oacute; gi&aacute; trị V cao nhất l&agrave;m bước đi tốt nhất.</p> <h1>Phương ph&aacute;p Đ&aacute;nh gi&aacute; chiến thuật</h1> <p>Phương ph&aacute;p thứ hai l&agrave; đ&aacute;nh gi&aacute; chiến thuật. Một chiến thuật sẽ cho ch&uacute;ng ta biết phải l&agrave;m g&igrave; từ một trạng th&aacute;i cụ thể.</p> <p>[latexpage]\[a_{t}=\pi _{\theta}(s_{t})\]</p> <p>Ch&uacute;ng ta c&oacute; thể đ&aacute;nh gi&aacute; một chiến thuật ngẫu nhi&ecirc;n li&ecirc;n tục để t&iacute;nh to&aacute;n c&aacute;c h&agrave;m gi&aacute; trị của n&oacute;. Chiến thuật ngẫu nhi&ecirc;n chỉ đơn giản l&agrave; một chiến thuật thực hiện bất kỳ một h&agrave;nh động n&agrave;o c&oacute; thể xảy ra một c&aacute;ch ngẫu nhi&ecirc;n. H&atilde;y xem x&eacute;t một m&ecirc; cung kh&aacute;c với c&aacute;c lối ra ở ph&iacute;a tr&ecirc;n b&ecirc;n tr&aacute;i v&agrave; ph&iacute;a dưới b&ecirc;n phải. H&agrave;m gi&aacute; trị được t&iacute;nh như sau:</p> <p>[latexpage]\[V_{k+1}(s)= \sum_{a\in A}\pi (a|s)(R_{s}^{a}+\gamma V_{k}(s'))\]</p> <p>Đối với một chiến thuật ngẫu nhi&ecirc;n, mỗi h&agrave;nh động sẽ c&oacute; c&ugrave;ng một x&aacute;c suất. Với bốn h&agrave;nh động c&oacute; thể xảy ra l&agrave; l&ecirc;n, xuống, sang phải v&agrave; s&aacute;ng tr&aacute;i th&igrave; [latexpage]$\pi (a|s)$ l&agrave; 0,25 cho bất kỳ trạng th&aacute;i n&agrave;o.</p> <p><img class="aligncenter wp-image-6308 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-146.png" alt="Hoc-gia-tri" width="830" height="419" /></p> <p style="text-align: center;">Được chỉnh sửa từ <a href="https://mitpress.mit.edu/books/reinforcement-learning-second-edition">nguồn</a></p> <p>Đối với lần lặp thứ 3 b&ecirc;n dưới, V [2, 2] = -2,9: ch&uacute;ng ta sẽ trừ đi 1 cho mỗi vị tr&iacute; xung quanh (phần thường l&agrave; -1 cho mỗi bước đi) v&agrave; sau đ&oacute; th&igrave; t&iacute;nh gi&aacute; trị trung b&igrave;nh cộng.</p> <p><img class="aligncenter wp-image-6309 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-147.png" alt="Hoc-gia-tri" width="491" height="224" /></p> <p style="text-align: center;"><a href="https://jonathan-hui.medium.com/rl-value-learning-24f52b49c36d">Nguồn</a></p> <p>Khi ch&uacute;ng ta tiếp tục v&ograve;ng lặp, V sẽ đạt tới điểm hội tụ v&agrave; ch&uacute;ng ta c&oacute; thể sử dụng h&agrave;m gi&aacute; trị để x&aacute;c định lại chiến thuật tối ưu nhất.</p> <p><img class="aligncenter wp-image-6310 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-148.png" alt="Hoc-gia-tri" width="467" height="205" /></p> <p style="text-align: center;">Được chỉnh sửa từ <a href="https://jonathan-hui.medium.com/rl-value-learning-24f52b49c36d">nguồn</a></p> <h1>Phương ph&aacute;p V&ograve;ng lặp chiến thuật</h1> <p>Phương ph&aacute;p thứ ba l&agrave; v&ograve;ng lặp chiến thuật. Việc lặp lại chiến thuật thực hiện đ&aacute;nh gi&aacute; chiến thuật v&agrave; cải tiến chiến thuật theo một c&aacute;ch kh&aacute;c:</p> <ol> <li>Đ&aacute;nh gi&aacute; [latexpage]$V^{\pi}(s)$</li> <li>Đặt [latexpage]$\pi\leftarrow \pi'$</li> </ol> <p>Ch&uacute;ng ta li&ecirc;n tục đ&aacute;nh gi&aacute; chiến thuật hiện tại v&agrave; ch&uacute;ng ta cũng sẽ điều chỉnh vaf cải thiện chiến thuật trong mỗi bước đi.</p> <p><img class="aligncenter wp-image-6311 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-149.png" alt="Hoc-gia-tri" width="643" height="362" /></p> <p style="text-align: center;">Được chỉnh sửa từ <a href="https://jonathan-hui.medium.com/rl-value-learning-24f52b49c36d">nguồn</a></p> <p>Khi ch&uacute;ng ta tiếp tục cải thiện chiến thuật, n&oacute; sẽ hội tụ tới điểm m&agrave; c&oacute; chiến thuật tối ưu nhất.</p> <p><img class="aligncenter wp-image-6313 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/a-7.png" alt="Hoc-gia-tri" width="770" height="233" /></p> <p style="text-align: center;"><a href="https://mitpress.mit.edu/books/reinforcement-learning-second-edition">Nguồn</a></p> <p>Đ&acirc;y l&agrave; v&iacute; dụ m&agrave; ch&uacute;ng ta c&oacute; thể t&igrave;m thấy chiến thuật tối ưu sau bốn v&ograve;ng lặp, nhanh hơn nhiều so với việc đ&aacute;nh gi&aacute; chiến thuật.</p> <p><img class="aligncenter wp-image-6314 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-150.png" alt="Hoc-gia-tri" width="845" height="416" /></p> <p style="text-align: center;">Được chỉnh sửa từ <a href="https://mitpress.mit.edu/books/reinforcement-learning">nguồn</a></p> <h2>Thuật to&aacute;n</h2> <p>H&agrave;m gi&aacute; trị tại bước thời gian i + 1 bằng:</p> <p>[latexpage]\[V_{i+1}^{\pi _{k}}(s)\leftarrow\sum_{s'}P(s'|s,\pi _{k}(s))\left [ R(s,\pi(s),s')+\gamma V_{i}^{\pi _{k}}(s') \right ]\]</p> <p>Trong đ&oacute; P l&agrave; m&ocirc; h&igrave;nh (m&ocirc; h&igrave;nh tổng qu&aacute;t h&oacute;a) sẽ x&aacute;c định trạng th&aacute;i tiếp theo sau khi thực hiện một h&agrave;nh động. chiến thuật được điều chỉnh lại sẽ l&agrave;:</p> <p>[latexpage]\[\pi _{k+1}(s)\leftarrow argmax_{a} \sum_{s'}P(s'|s,a)\left [ R(s,a,s')+\gamma V^{\pi _{k}}(s') \right ]\]</p> <p>Đối với một m&ocirc; h&igrave;nh tất định, phương tr&igrave;nh c&oacute; thể được đơn giản h&oacute;a th&agrave;nh:</p> <p>[latexpage]\[V^{\pi}\leftarrow r(s,\pi(s))+\gamma E_{s'\sim p(s'|s,\pi (s))}\left [ V^{\pi}(s') \right ]\]</p> <p>[latexpage]\[\pi'(a_{t}|s_{t})=\left\{\begin{matrix}1 \;\; if \;\; a_{t}=argmax_{a_{t}}A^{\pi}(s_{t},a_{t})\\ 0 \;\;otherwise\end{matrix}\right\]</p> <p>Sau đ&acirc;y l&agrave; luồng hoạt động chung của thuật to&aacute;n</p> <p><img class="aligncenter wp-image-6315 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-151.png" alt="Hoc-gia-tri" width="848" height="357" /></p> <h1>Phương tr&igrave;nh tối ưu Bellman</h1> <p>Trong phần trước, ch&uacute;ng ta sử dụng lập tr&igrave;nh động để học đ&aacute;nh gi&aacute; (value learning) theo phương thức lặp. Phương tr&igrave;nh dưới đ&acirc;y thường được đề cập trong RL v&agrave; được gọi l&agrave; r&agrave;ng buộc phương tr&igrave;nh Bellman.</p> <p>[latexpage]\[V_{k}^{*}(s)=max_{a}E\left [ R_{t+1}+\gamma V*(S_{t+1})|S_{t}=s,A_{t}=a \right ]\]</p> <p>[latexpage]\[V_{k}^{*}(s)=max_{a}\sum_{s',r}p(s',r|s,a)\left [r+\gamma V*(s') \right ]\]</p> <h1>Học h&agrave;m gi&aacute; trị kết hợp với m&ocirc; h&igrave;nh ngẫu nhi&ecirc;n</h1> <p>Trong phương ph&aacute;p&nbsp;v&ograve;ng lặp gi&aacute; trị ở v&iacute; dụ trước, ch&uacute;ng ta truyền ph&eacute;p t&iacute;nh gi&aacute; trị tối ưu V * cho c&aacute;c vị tr&iacute; xung quanh của n&oacute; trong mỗi lần lặp</p> <p><img class="aligncenter wp-image-6316 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-152.png" alt="Hoc-gia-tri" width="728" height="173" /></p> <p style="text-align: center;">Được chỉnh sửa từ <a href="https://jonathan-hui.medium.com/rl-value-learning-24f52b49c36d">nguồn</a></p> <p>sử dụng ph&eacute;p to&aacute;n sau:</p> <p>[latexpage]\[V_{k}^{*}(s)=max_{a}\sum_{s'}P(s'|s,a)(R(s,a,s')+\gamma V_{k-1}^{*}(s'))\]</p> <p>Trong những v&iacute; dụ đ&oacute;, m&ocirc; h&igrave;nh P c&oacute; t&iacute;nh tất định v&agrave; đ&atilde; được biết. P đều bằng 0 ngoại trừ một trạng th&aacute;i (s&rsquo;) c&oacute; gi&aacute; trị l&agrave; một. Do đ&oacute;, n&oacute; được viết ngắn gọn &nbsp;th&agrave;nh:</p> <p>[latexpage]\[V^{*}(s)=max_{a}(r+\gamma V^{*}(s'))\]</p> <p>Nhưng đối với m&ocirc; h&igrave;nh ngẫu nhi&ecirc;n, ch&uacute;ng ta cần xem x&eacute;t tất cả c&aacute;c trạng th&aacute;i c&oacute; thể c&oacute; trong tương lai.</p> <p>[latexpage]\[V_{k}^{*}(s)=max_{a}\sum_{s'}P(s'|s,a)(R(s,a,s')+\gamma V_{k-1}^{*}(s'))\]</p> <p>[latexpage]\[\pi _{k}^{*}(s)\leftarrow argmax_{a}\sum_{s'}P(s'|s,a)(R(s,a,s')+\gamma V_{k-1}^{*}(s'))\]</p> <p>H&atilde;y c&ugrave;ng minh họa bằng một v&iacute; dụ m&ecirc; cung c&oacute; sử dụng m&ocirc; h&igrave;nh ngẫu nhi&ecirc;n. M&ocirc; h&igrave;nh n&agrave;y c&oacute; gi&aacute; trị nhiễu l&agrave; 0,2. Nếu ch&uacute;ng ta sang phải, th&igrave; c&oacute; 0,8 khả năng l&agrave; chắc chắn ch&uacute;ng ta sẽ sang phải. Nhưng c&oacute; 0,1 khả năng l&agrave; ch&uacute;ng ta đi l&ecirc;n v&agrave; 0,1 khả năng ch&uacute;ng ta đi xuống. Nếu ch&uacute;ng ta chạm phải đường bi&ecirc;n, ch&uacute;ng ta sẽ bật trở lại vị tr&iacute; ban đầu.</p> <p><img class="aligncenter wp-image-6327 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-153.png" alt="Hoc-gia-tri" width="958" height="455" /></p> <p style="text-align: center;">Được chỉnh sửa từ <a href="https://drive.google.com/file/d/0BxXI_RttTZAhVXBlMUVkQ1BVVDQ/view">nguồn</a></p> <p>Ch&uacute;ng ta sẽ giả định hệ số khấu hao &gamma; sẽ l&agrave; 0,9 v&agrave; ch&uacute;ng ta nhận được phần thưởng bằng 0 cho mỗi bước đi trừ khi ch&uacute;ng ta đạt đến trạng th&aacute;i kết th&uacute;c l&agrave; +1 cho điểm m&agrave;u xanh l&aacute; v&agrave; -1 cho điểm m&agrave;u đỏ ở b&ecirc;n tr&ecirc;n.</p> <p>H&atilde;y c&ugrave;ng chuyển tới v&ograve;ng lặp thứ 5 v&agrave; xem c&aacute;ch t&iacute;nh V * [2, 3] (được gạch ch&acirc;n m&agrave;u trắng trong h&igrave;nh b&ecirc;n dưới) dựa tr&ecirc;n kết quả của v&ograve;ng lặp thứ 4.</p> <p><img class="aligncenter wp-image-6329 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-154.png" alt="Hoc-gia-tri" width="927" height="410" /></p> <p style="text-align: center;">Được chỉnh sửa từ <a href="https://drive.google.com/file/d/0BxXI_RttTZAhVXBlMUVkQ1BVVDQ/view">nguồn</a></p> <p>Trạng th&aacute;i [2, 3] c&oacute; gi&aacute; trị V cao nhất. V&igrave; vậy, h&agrave;nh động tối ưu cho V * [2, 3] sẽ l&agrave; đi l&ecirc;n. H&agrave;m gi&aacute; trị mới l&agrave;:</p> <p><img class="aligncenter wp-image-6330 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-155.png" alt="Hoc-gia-tri" width="839" height="442" /></p> <p style="text-align: center;">Được chỉnh sửa từ <a href="https://jonathan-hui.medium.com/rl-value-learning-24f52b49c36d">nguồn</a></p> <p>Trong mỗi v&ograve;ng lặp, ch&uacute;ng ta sẽ t&iacute;nh lại V * cho mọi vị tr&iacute; ngoại trừ trạng th&aacute;i cuối c&ugrave;ng. Khi ch&uacute;ng ta tiếp tục lặp lại, V * sẽ hội tụ. V&iacute; dụ, V * [2, 3] sẽ hội tụ tại 0,57.</p> <p><img class="aligncenter wp-image-6331 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-156.png" alt="Hoc-gia-tri" width="445" height="422" /></p> <p style="text-align: center;">Được chỉnh sửa từ <a href="https://drive.google.com/file/d/0BxXI_RttTZAhVXBlMUVkQ1BVVDQ/view">nguồn</a></p> <h2>Thuật to&aacute;n</h2> <p>Sau đ&acirc;y l&agrave; đoạn giả m&atilde; cho phương ph&aacute;p v&ograve;ng lặp gi&aacute; trị:</p> <p>Bắt đầu với [latexpage]$V_{0}^{*}(s)=0$ cho tất cả gi&aacute; trị s<br />For k=1,..,H:<br />for tất cả trạng th&aacute;i s trong S:<br />[latexpage]$V_{k}^{*}(s)\leftarrow max_{a}\sum_{s'}P(s'|s,a)(R(s,a,s')+ \gamma V_{k-1}^{*}(s'))$<br />[latexpage]$\pi _{k}^{*}(s)\leftarrow argmax_{a}\sum_{s'}P(s'|s,a)(R(s,a,s')+ \gamma V_{k-1}^{*}(s'))$</p> <h1>Phương ph&aacute;p Kh&ocirc;ng sử dụng m&ocirc; h&igrave;nh</h1> <p>Bất kể đ&oacute; l&agrave; m&ocirc; h&igrave;nh tất định hay m&ocirc; h&igrave;nh ngẫu nhi&ecirc;n, ch&uacute;ng ta cần một m&ocirc; h&igrave;nh P để t&iacute;nh to&aacute;n h&agrave;m gi&aacute; trị hoặc để c&oacute; được chiến thuật tối ưu.</p> <p>[latexpage]\[V_{k}^{*}(s)=max_{a}\sum_{s'}P(s'|s,a)(R(s,a,s')+\gamma V_{k-1}^{*}(s'))\]</p> <p>[latexpage]\[\pi _{k}^{*}(s)\leftarrow argmax_{a}\sum_{s'}P(s'|s,a)(R(s,a,s')+ \gamma V_{k-1}^{*}(s'))\]</p> <h2>Phương ph&aacute;p Monte-Carlo</h2> <p>Bất cứ khi n&agrave;o ch&uacute;ng ta kh&ocirc;ng biết m&ocirc; h&igrave;nh, ch&uacute;ng ta sẽ quay lại việc lấy mẫu v&agrave; sử dụng quan s&aacute;t để ước t&iacute;nh tổng phần thưởng nhận được. Bắt đầu từ trạng th&aacute;i ban đầu, ch&uacute;ng ta thực hiện chiến thuật v&agrave; quan s&aacute;t tổng phần thưởng G thu được.</p> <p>[latexpage]\[(s_{1},a_{1},r_{1},s_{2},a_{2},r_{2},...,s_{H},a_{H},r_{H})\]</p> <p>G sẽ l&agrave;:</p> <p>[latexpage]\[V^{\pi}(s_{t})\approx \sum_{t'=t}^{T}r(s_{t'},a_{t'})\]</p> <p>Nếu chiến thuật hoặc m&ocirc; h&igrave;nh l&agrave; ngẫu nhi&ecirc;n, th&igrave; tổng phần thưởng m&agrave; đ&atilde; được lấy mẫu c&oacute; thể sẽ nhận gi&aacute; trị kh&aacute;c nhau trong mỗi lần chạy. Ch&uacute;ng ta c&oacute; thể chạy v&agrave; kh&ocirc;i phục lại hệ thống nhiều lần để t&igrave;m gi&aacute; trị trung b&igrave;nh V(S). Hoặc ch&uacute;ng ta c&oacute; thể chỉ cần giữ lại một gi&aacute; trị trung b&igrave;nh trong lần chạy như c&ocirc;ng thức b&ecirc;n dưới thay v&igrave; phải giữ lại tất cả c&aacute;c kết quả đ&atilde; được lấy mẫu trước đ&oacute;.</p> <p>[latexpage]\[V_{\pi}(S_{t})=V_{\pi}(S_{t})+\alpha(G_{t}-V_{\pi}(S_{t}))\]</p> <p>Ch&uacute; &yacute;: Phương ph&aacute;p Monte-Carlo lấy mẫu cho c&aacute;c h&agrave;nh động cho đến khi kết th&uacute;c một Episode (một chuỗi c&aacute;c trạng th&aacute;i v&agrave; h&agrave;nh động cho đến trạng th&aacute;i kết th&uacute;c&nbsp;s1,a1,s2,a2,...sT,aT) để t&iacute;nh xấp xỉ cho tổng phần thưởng nhận được.</p> <h2>Kiểm so&aacute;t Monte-Carlo</h2> <p>Ngay cả khi ch&uacute;ng ta c&oacute; thể t&iacute;nh được V (S) bằng c&aacute;ch lấy mẫu, l&agrave;m thế n&agrave;o ch&uacute;ng ta c&oacute; thể quyết định được một h&agrave;nh động từ trạng th&aacute;i n&agrave;y sang trạng th&aacute;i kh&aacute;c?</p> <p>[latexpage]\[\pi _{k}^{*}(s)\leftarrow argmax_{a}\sum_{s'}P(s'|s,a)(R(s,a,s')+ \gamma V_{k-1}^{*}(s'))\]</p> <p>Nếu như kh&ocirc;ng biết m&ocirc; h&igrave;nh, ch&uacute;ng ta sẽ kh&ocirc;ng biết h&agrave;nh động n&agrave;o c&oacute; thể đưa ch&uacute;ng ta đến trạng th&aacute;i tối ưu tiếp theo. V&iacute; dụ: nếu kh&ocirc;ng c&oacute; biển b&aacute;o đường (m&ocirc; h&igrave;nh), ch&uacute;ng ta sẽ kh&ocirc;ng biết l&agrave;n đường b&ecirc;n tr&aacute;i hay l&agrave;n b&ecirc;n phải của đường cao tốc đưa ch&uacute;ng ta đến SM hoặc WSM?</p> <p><img class="aligncenter wp-image-6332 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-157.png" alt="Hoc-gia-tri" width="976" height="321" /></p> <h2>Học gi&aacute; trị dựa tr&ecirc;n h&agrave;nh động</h2> <p>Điều n&agrave;y n&oacute;i đến h&agrave;m gi&aacute; trị dựa tr&ecirc;n h&agrave;nh động, l&agrave; họ h&agrave;ng với h&agrave;m gi&aacute; trị nhưng kh&ocirc;ng cần sử dụng đến m&ocirc; h&igrave;nh. Thay v&igrave; đo lường mức độ tốt của một trạng th&aacute;i (state) V(s), ch&uacute;ng ta sẽ đo lường mức độ để thực hiện một h&agrave;nh động ở trạng th&aacute;i Q (s, a). V&iacute; dụ: khi ch&uacute;ng ta ở SB, ch&uacute;ng ta sẽ kh&ocirc;ng biết được về lợi &iacute;ch của việc đi l&agrave;n b&ecirc;n phải hay l&agrave;n b&ecirc;n tr&aacute;i tr&ecirc;n đường 101 mặc d&ugrave; ch&uacute;ng ta kh&ocirc;ng biết đường đ&oacute; sẽ dẫn ch&uacute;ng ta đến đ&acirc;u. V&igrave; vậy, ở bất kỳ trạng th&aacute;i n&agrave;o, ch&uacute;ng ta chỉ c&oacute; thể thực hiện h&agrave;nh động với gi&aacute; trị Q l&agrave; cao nhất. Điều n&agrave;y cho ph&eacute;p ch&uacute;ng ta thực hiện m&agrave; kh&ocirc;ng cần m&ocirc; h&igrave;nh. Với trạng th&aacute;i c&oacute; k h&agrave;nh động c&oacute; thể thực hiện được, th&igrave; b&acirc;y giờ ch&uacute;ng ta cũng c&oacute; k gi&aacute; trị Q.</p> <p><img class="aligncenter wp-image-6334 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-158.png" alt="Hoc-gia-tri" width="1009" height="354" /></p> <p>H&agrave;m gi&aacute; trị Q (h&agrave;m gi&aacute; trị dựa tr&ecirc;n h&agrave;nh động) được định nghĩa l&agrave; phần thưởng kỳ vọng cho một h&agrave;nh động dựa tr&ecirc;n một chiến thuật n&agrave;o đ&oacute;.</p> <p>[latexpage]\[Q(s_{t},a_{t})=\sum_{t'=t}^{T}E_{\pi _{\theta}}\left [ r(s_{t'},a_{t'})|s_{t},a_{t} \right ]\]</p> <p>Tương tự như phần trước, ch&uacute;ng ta c&oacute; thể sử dụng phương ph&aacute;p Monte-Carlo để t&igrave;m ra Q.</p> <p>[latexpage]\[Q(S_{t},A_{t})=Q(S_{t},A_{t})+\alpha (G_{t}-Q(S_{t},A_{t}))\]</p> <p>Trong v&iacute; dụ của ch&uacute;ng ta, ch&uacute;ng ta sẽ tiếp tục đi b&ecirc;n l&agrave;n đường b&ecirc;n tr&aacute;i khi ch&uacute;ng ta ở SB.</p> <p><img class="aligncenter wp-image-6335 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-159.png" alt="Hoc-gia-tri" width="1009" height="356" /></p> <p>Đ&acirc;y l&agrave; phương ph&aacute;p Monte-Carlo cho h&agrave;m gi&aacute; trị Q.</p> <h2>V&ograve;ng lặp chiến thuật c&ugrave;ng với h&agrave;m gi&aacute; trị Q</h2> <p>Ch&uacute;ng ta c&oacute; thể &aacute;p dụng h&agrave;m gi&aacute; trị Q c&ugrave;ng với phương ph&aacute;p v&ograve;ng lặp chiến thuật. Sau đ&acirc;y l&agrave; luồng hoạt động:</p> <p><img class="aligncenter wp-image-6336 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/Capture-160.png" alt="Hoc-gia-tri" width="998" height="406" /></p> <h1>Vấn đề đặt ra</h1> <p>Giải ph&aacute;p được tr&igrave;nh b&agrave;y ở đ&acirc;y c&oacute; một số vấn đề. Đầu ti&ecirc;n, n&oacute; kh&ocirc;ng thể mở rộng cho một kh&ocirc;ng gian trạng th&aacute;i lớn. Bộ nhớ để ghi lại c&aacute;c gi&aacute; trị V hoặc Q cho mỗi trạng th&aacute;i l&agrave; kh&ocirc;ng khả thi. Ch&uacute;ng ta c&oacute; thể x&acirc;y dựng một bộ ước lượng h&agrave;m cho c&aacute;c h&agrave;m gi&aacute; trị để tiết kiệm bộ nhớ, giống như m&ocirc; h&igrave;nh mạng học s&acirc;u cho việc ph&acirc;n loại kh&ocirc;ng? Thứ hai, phương ph&aacute;p Monte-Carlo c&oacute; phương sai rất cao. chiến thuật ngẫu nhi&ecirc;n c&oacute; thể t&iacute;nh to&aacute;n c&aacute;c kết quả phần thưởng rất kh&aacute;c nhau trong c&aacute;c lần chạy kh&aacute;c nhau. Kết quả đầu ra với phương sai cao sẽ l&agrave;m ảnh hưởng kh&ocirc;ng tốt đến qu&aacute; tr&igrave;nh đ&agrave;o tạo. L&agrave;m thế n&agrave;o để đ&agrave;o tạo m&ocirc; h&igrave;nh sao cho đảm bảo việc hội tụ (đạt được mức tối ưu nhất) tốt hơn?</p> <h1>T&oacute;m tắt</h1> <p>H&atilde;y t&oacute;m tắt lại những g&igrave; ch&uacute;ng ta học được về phương ph&aacute;p học gi&aacute; trị. Ch&uacute;ng ta muốn t&igrave;m một chiến thuật tối ưu c&oacute; thể tối đa h&oacute;a phần thưởng khấu hao kỳ vọng.</p> <p>[latexpage]\[V^{*}(s)=max_{\pi}E\left [ \sum_{t=0}^{H} \gamma ^{t}R(s_{t},a_{t},s_{t+1})|\pi, s_{0}=s \right ]\]</p> <p>Ch&uacute;ng ta c&oacute; thể giải quyết n&oacute; bằng c&aacute;ch t&iacute;nh h&agrave;m gi&aacute; trị hoặc h&agrave;m gi&aacute; trị Q:</p> <p>[latexpage]\[V_{\pi}(s)=E_{\pi}\left [ \sum_{k=0}^{\infty} \gamma ^{k}R_{t+k+1}|S_{t}=s \right ]\]</p> <p>[latexpage]\[Q_{\pi}(s,a)=E_{\pi}\left [ \sum_{k=0}^{\infty} \gamma ^{k}R_{t+k+1}|S_{t}=s,A_{t}=a \right ]\]</p> <p>V&agrave; điều n&agrave;y c&oacute; thể được giải quyết bằng c&aacute;ch sử dụng phương ph&aacute;p lập tr&igrave;nh động:</p> <p>[latexpage]\[V_{k+1}(s) = E_{\pi}\left [ R_{t+1}+\gamma V_{k}(S_{t+1})|S_{t}=s \right ]\]</p> <p>[latexpage]\[V_{k+1}(s) = \sum_{a}\pi(a|s)\sum_{s',r}p(s',r|s,a)\left [ r+ \gamma V_{k}(s') \right ]\]</p> <p>Hoặc sử dụng phương ph&aacute;p dự đo&aacute;n trước 1 bước được gọi l&agrave; Temporal Difference (TD).</p> <p>[latexpage]\[Q^{*}(s,a)=E\left [ R_{t+1} + \gamma max_{a'} Q^{*}(S_{t+1},a')|S_{t}=s, A_{t}=a \right ]\]</p> <p>[latexpage]\[Q^{*}(s,a)= \sum_{s',r}p(s',r|s,a)\left [ r+\gamma max_{a'}Q^{*}(s',a') \right ]\]</p> <p>H&atilde;y theo d&otilde;i phần tiếp theo, ch&uacute;ng ta sẽ giải quyết một số vấn đề đ&atilde; đề cập trước đ&oacute; v&agrave; &aacute;p dụng ch&uacute;ng v&agrave;o thực tế.</p> <p>P/s: Mong mọi người lu&ocirc;n ủng hộ <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>