نگاهی (طولانی) به یادگیری تقویتی – بخش دوم

متن زیر ترجمه A (Long) Peek into Reinforcement Learning است.

سایر بخش های این مقاله را در لینک های زیر در دسترس هستند

بخش اول

فهرست

فرآیندهای تصمیم‌گیری مارکوف

به بیان رسمی‌تر، تقریباً تمام مسائل RL را می‌توان به عنوان فرآیندهای تصمیم گیری مارکوف (MDP) در نظر گرفت. تمام حالت‌ها در MDP دارای ویژگی "مارکوف" هستند، با اشاره به این واقعیت که آینده فقط به وضعیت فعلی بستگی دارد، نه گذشته:$$P\left[S_{t+1}\right|S_t]=P[S_{t+1}|S_1,\dots ,S_t]$$

یا به عبارت دیگر، آینده و گذشته با توجه به زمان حال به طور مشروط مستقل هستند ، زیرا وضعیت فعلی تمام آماری را که برای تصمیم گیری در مورد آینده نیاز داریم در بر می‌گیرد.

فرآیند تصمیم گیری مارکف از پنج عنصر تشکیل شده است

$M=⟨S,A,P,R,\gamma ⟩$

که در آن نمادها همان مفاهیم کلیدی در بخش قبل را دارند و به خوبی با تنظیمات مشکل RL همسو می شوند:

• $S$ مجموعه ای از حالات
• $A$ مجموعه ای از اقدامات
• $P$ تابع احتمال انتقال
• $\gamma$ عامل تخفیف برای پاداش های آینده. در یک محیط ناشناخته، ما دانش کاملی در مورد $P$ و $R$ آن نداریم

معادلات بلمن

معادلات بلمن به مجموعه‌ای از معادلات اشاره دارد که تابع ارزش را به پاداش فوری به اضافه ارزش‌های آتی تخفیف‌دار تجزیه می‌کند.

$$ \begin{aligned} V(s) &= \mathbb{E}[G_t \vert S_t = s] \\ &= \mathbb{E} [R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots \vert S_t = s] \\ &= \mathbb{E} [R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + \dots) \vert S_t = s] \\ &= \mathbb{E} [R_{t+1} + \gamma G_{t+1} \vert S_t = s] \\ &= \mathbb{E} [R_{t+1} + \gamma V(S_{t+1}) \vert S_t = s] \end{aligned} $$

به طور مشابه برای Q-value،

$$ \begin{aligned} Q(s, a) &= \mathbb{E} [R_{t+1} + \gamma V(S_{t+1}) \mid S_t = s, A_t = a] \\ &= \mathbb{E} [R_{t+1} + \gamma \mathbb{E}_{a\sim\pi} Q(S_{t+1}, a) \mid S_t = s, A_t = a] \end{aligned} $$

معادلات انتظار بلمن

فرآیند به‌روزرسانی بازگشتی را می‌توان بیشتر تجزیه کرد تا معادلاتی باشد که بر روی هر دو توابع حالت-مقدار و اقدام-مقدار ساخته شده‌اند. همانطور که در مراحل اقدام آینده پیش می رویم، V و Q را به طور متناوب با پیروی از خط مشی $\pi$ گسترش می‌دهیم

$$\begin{array}{c}{V}_{\pi }\left(s\right)\mathrm{=\sum a\in A\pi (a|s)Q\pi (s,a)}{Q}_{\pi }(s,a)\mathrm{=R(s,a)+\gamma \sum s\prime \in SPass\prime V\pi (s\prime )}{V}_{\pi }\left(s\right)\mathrm{=\sum a\in A\pi (a|s)(R(s,a)+\gamma \sum s\prime \in SPass\prime V\pi (s\prime ))}{Q}_{\pi }(s,a)\mathrm{=R(s,a)+\gamma \sum s\prime \in SPass\prime \sum a\prime \in A\pi (a\prime |s\prime )Q\pi (s\prime ,a\prime )}& $ \begin{array}{c}{V}_{\pi }\left(s\right)=\sum _{a\in A}\pi \left(a\right|s\left)Q_{\pi }\right(s,a)& Q_{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}_{\pi }\left(s^{\prime }\right)& V_{\pi }\left(s\right)=\sum _{a\in A}\pi \left(a\right|s\left)(R\right(s,a)+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}_{\pi }(s^{\prime }))& Q_{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a\sum _{a^{\prime }\in A}\pi \left(a^{\prime }\right|s^{\prime }\left)Q_{\pi }\right(s^{\prime },a^{\prime })\end{array}$\end{array}$$

معادلات بهینه‌سازی بلمن

اگر ما فقط به مقادیر بهینه علاقه‌مند باشیم، به جای محاسبه انتظارات منتج از یک خط مشی، می‌توانیم بدون استفاده از یک خط مشی، در طول بروزرسانی‌های جایگزین، مستقیماً به حداکثر بازده بپردازیم. به طور خلاصه: مقادیر بهینه V ∗ و Q ∗ بهترین بازده‌هایی هستند که می‌توانیم به دست آوریم، که در اینجا تعریف شده‌اند.

$$\begin{array}{c}{V}_{\ast }\left(s\right)\mathrm{=maxa\in AQ\ast (s,a)}{Q}_{\ast }(s,a)\mathrm{=R(s,a)+\gamma \sum s\prime \in SPass\prime V\ast (s\prime )}{V}_{\ast }\left(s\right)\mathrm{=maxa\in A(R(s,a)+\gamma \sum s\prime \in SPass\prime V\ast (s\prime ))}{Q}_{\ast }(s,a)\mathrm{=R(s,a)+\gamma \sum s\prime \in SPass\prime maxa\prime \in AQ\ast (s\prime ,a\prime )}& $ \begin{array}{c}{V}_{\ast }\left(s\right)=\underset{a\in A}{max}{Q}_{\ast }(s,a)& Q_{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}_{\ast }\left(s^{\prime }\right)& V_{\ast }\left(s\right)=\underset{a\in A}{max}(R(s,a)+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}_{\ast }\left(s^{\prime }\right))& Q_{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a\underset{a^{\prime }\in A}{max}{Q}_{\ast }(s^{\prime },a^{\prime })\\ $ \begin{array}{c}{V}_{\ast }\left(s\right)=\underset{a\in A}{max}{Q}_{\ast }(s,a)& Q_{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}_{\ast }\left(s^{\prime }\right)& V_{\ast }\left(s\right)=\underset{a\in A}{max}(R(s,a)+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}_{\ast }\left(s^{\prime }\right))& Q_{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a\underset{a^{\prime }\in A}{max}{Q}_{\ast }(s^{\prime },a^{\prime })\end{array}$\end{array}$\end{array}$$

جای تعجب نیست که آنها بسیار شبیه معادلات انتظار بلمن هستند.

اگر اطلاعات کاملی از محیط داشته باشیم، به یک مشکل برنامه‌ریزی تبدیل می‌شود که توسط DP قابل حل است. متأسفانه، در اکثر سناریوها، ما $P_{s{s}^{\prime }}^a$ یا $R(s,a)$ نمی‌دانیم

 بنابراین ما نمی‌توانیم MDPها را با استفاده مستقیم از معادلات بلمن حل کنیم، اما پایه‌ی نظری بسیاری از الگوریتم‌های RL را می‌گذارد.