採用赵世钰老師的 RL 課程和 Sutton & Barto 的書混合筆記
之前學的 truncated policy iteration 演算法, 需要知道 model dynamics $p(s',r|s,a)$:
$$ p(s',r|s,a)\triangleq Pr\{S_t=s',R_t=r|S_{t-1}=s,A_{t-1}=a\} $$
就是 environment 的上述 pdf 要知道.
不過這不切實際, 如果我們能從經驗上 (data) 直接學習 optimal policy 的話, 那會實際很多
MC-based RL 的 motivation 就是只要 environment 能採樣出 episodes 的話, 就能學 optimal policy.
https://www.youtube.com/watch?v=q1rTQXd1p-c&list=PLEhdbSEZZbDYwsXT1NeBZbmPCbIIqlgLS&index=17
先介紹 MC Basic: The simplest MC-based algorithm 這個方法
簡單說就是把 policy iteration 裡面 model 的地方 ( $q_{\pi_k}(s,a)$ ) 換成 model-free
可以看出不管是 PE or PI 兩個 steps 都依賴於計算 $q_{\pi_k}(s,a)$.
如果不使用 Bellman equation 來計算 (因為沒有 model dynamics), 改採最原始的定義, 那就可以透過採樣來估計:
$$ q_{\pi_k}(s,a)=\mathbb{E}\left[G_t|S_t=s,A_t=a\right] $$
簡單講, 對每一個 $s\in S,a\in A$ 來說要找出 $N$ 條從 $(s,a)$ 出發的 trajectory (episode), 每一條都算出 return, 然後平均 return 後就當作是期望值. 可想而知這會非常沒有效率, 之後再介紹怎麼改善效率.
所以 MC Basic 算法就很容易, 如下: