Monte-Carlo Prediction
1. Model-Free
์ด์ ์ฑํฐ์์ Dynamic Programming์ ๋ํด์ ๋ฐฐ์๋ณด์์ต๋๋ค. Dynamic programming์ Bellman Equation์ ํตํด์ optimalํ ํด๋ฅผ ์ฐพ์๋ด๋ ๋ฐฉ๋ฒ์ผ๋ก์ MDP์ ๋ํ ๋ชจ๋ ์ ๋ณด๋ฅผ ๊ฐ์ง ์ํ์์ ๋ฌธ์ ๋ฅผ ํ์ด๋๊ฐ๋ ๋ฐฉ๋ฒ์ ์ด์ผ๊ธฐํฉ๋๋ค.
ํนํ Environment์ model์ธ "Reward function"๊ณผ "state transition probabilities"๋ฅผ ์์์ผํ๊ธฐ ๋๋ฌธ์ Model-basedํ ๋ฐฉ๋ฒ์ด๋ผ๊ณ ํ ์ ์์ต๋๋ค. ์ด๋ฌํ ๋ฐฉ๋ฒ์๋ ์๋๊ณผ ๊ฐ์ ๋ฌธ์ ์ ์ด ์์ต๋๋ค.
(1) Full-width Backup --> expensive computation (2) Full knowledge about Environment
์ด๋ฌํ ๋ฐฉ์์ผ๋ก๋ ๋ฐ๋๊ฐ์ ๊ฒฝ์ฐ์ ์๊ฐ ๋ง์ ๋ฌธ์ ๋ฅผ ํ ์๊ฐ ์๊ณ ์ค์ฌ ์ธ์์ ์ ์ฉ์ํฌ ์๊ฐ ์์ต๋๋ค. ์ฌ์ค ์์ ๊ฐ์ด ํ๋ฌธ์ ์ผ๋ก ์ ๊ทผํ์ง ์๋๋ผ๋ ์ด๋ฌํ ๋ฐฉ๋ฒ์ด ์ฌ๋์ด ๋ฐฐ์ฐ๋ ๋ฐฉ๋ฒ๊ณผ ๋ง์ด ๋ค๋ฅด๋ค๋ ๊ฒ์ ์ ์ ์์ต๋๋ค. ์ด์ ์๋ ์ธ๊ธํ์์ง๋ง ์ฌ๋์ ๋ชจ๋ ๊ฒ์ ๋ค ์ ํ์ ์์ง์ด์ง ์์ต๋๋ค. ๋ง์ ธ๋ณด๋ฉด์, ๋ฐ์๋ณด๋ฉด์ ์กฐ๊ธ์ฉ ๋ฐฐ์๋๊ฐ๋๋ค. ์ด์ ์๋ ๋งํ๋ฏ์ด Trial and error๋ฅผ ํตํด์ ํ์ตํ๋ ๊ฒ์ด ๊ฐํํ์ต์ ํฐ ํน์ง์ ๋๋ค.
๋ฐ๋ผ์ DP์ฒ๋ผ full-width backup์ ํ๋ ๊ฒ์ด ์๋๋ผ ์ค์ฌ๋ก ๊ฒฝํํ ์ ๋ณด๋ค๋ก์ update๋ฅผ ํ๋ sample backup์ ํ๊ฒ ๋ฉ๋๋ค. ์ด๋ ๊ฒ ์ค์ฌ๋ก ๊ฒฝํํ ์ ๋ณด๋ค์ ์ฌ์ฉํจ์ผ๋ก์ ์ฒ์๋ถํฐ environment์ ๋ํด์ ๋ชจ๋ ๊ฒ์ ์ ํ์๊ฐ ์์ต๋๋ค. Environment์ model์ ๋ชจ๋ฅด๊ณ ํ์ตํ๊ธฐ ๋๋ฌธ์ Model-free๋ผ๋ ๋ง์ด ๋ถ๊ฒ ๋ฉ๋๋ค.

ํ์ฌ์ policy๋ฅผ ๋ฐํ์ผ๋ก ์์ง์ฌ๋ณด๋ฉด์ sampling์ ํตํด value function์ updateํ๋ ๊ฒ์ model-free prediction์ด๋ผ ํ๊ณ policy๋ฅผ update๊น์ง ํ๊ฒ ๋๋ค๋ฉด model-free control์ด๋ผ๊ณ ํฉ๋๋ค.
์ด๋ ๊ฒ Sampling์ ํตํด์ ํ์ตํ๋ model-free ๋ฐฉ๋ฒ์๋ ๋ค์ ๋ ๊ฐ์ง๊ฐ ์์ต๋๋ค.
(1) Monte-Carlo (2) Temporal Difference
Monte-Carlo๋ episode๋ง๋ค updateํ๋ ๋ฐฉ๋ฒ์ด๊ณ Temporal Difference๋ time step๋ง๋ค updateํ๋ ๋ฐฉ๋ฒ์ ๋๋ค. ์ด๋ฒ chapter์์๋ Monte-Carlo Learning์ ์ดํด๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
2. Monte-Carlo
Monte-Carlo๋ผ๋ ๋ง์ ๋ํด์ Sutton ๊ต์๋์ ์ฑ ์์ ๋ค์๊ณผ ๊ฐ์ด ์ด์ผ๊ธฐํฉ๋๋ค.
The term "Monte Carlo" is often used more broadly for any estimation method whose operation involves a significant random component. Here we use it specifically for methods based on averaging complete returns
Monte-Carlo ๋จ์ด ์์ฒด๋ ๋ฌด์์ธ๊ฐ๋ฅผ randomํ๊ฒ ์ธก์ ํ๋ ๊ฒ์ ๋ปํ๋ ๋ง์ด๋ผ๊ณ ํฉ๋๋ค. ๊ฐํํ์ต์์๋ "averaging complete returns"ํ๋ ๋ฐฉ๋ฒ์ ์๋ฏธํ๋ค๊ณ ํฉ๋๋ค. ์ด๊ฒ์ ๋ฌด์์ ์๋ฏธํ ๊น์?
Monte-Carlo์ Temporal Difference๋ก ๊ฐ๋ฆฌ๋ ๊ฒ์ value function์ estimationํ๋ ๋ฐฉ๋ฒ์ ๋ฐ๋ผ์ ์ ๋๋ค. value function์ด๋ผ๋ ๊ฒ์ expected accumulative future reward๋ก์ ์ง๊ธ ์ด state์์ ์์ํด์ ๋ฏธ๋๊น์ง ๋ฐ์ ๊ธฐ๋๋๋ reward์ ์ดํฉ์ ๋๋ค. ์ด๊ฒ์ DP๊ฐ ์๋๋ผ๋ฉด ์ด๋ป๊ฒ ์ธก์ ํ ์ ์์๊น์?
๊ฐ์ฅ ๊ธฐ๋ณธ์ ์ธ ์๊ฐ์ episode๋ฅผ ๋๊น์ง ๊ฐ๋ณธ ํ์ ๋ฐ์ reward๋ค๋ก ๊ฐ state์ value function๋ค์ ๊ฑฐ๊พธ๋ก ๊ณ์ฐํด๋ณด๋ ๊ฒ์ ๋๋ค. ๋ฐ๋ผ์ MC(Monte-Carlo)๋ ๋๋์ง ์๋ episode์์๋ ์ฌ์ฉํ ์ ์๋ ๋ฐฉ๋ฒ์ ๋๋ค. initial state S1์์๋ถํฐ ์์ํด์ terminal state St๊น์ง ํ์ฌ policy๋ฅผ ๋ฐ๋ผ์ ์์ง์ด๊ฒ ๋๋ค๋ฉด ํ time step๋ง๋ค reward๋ฅผ ๋ฐ๊ฒ ๋ ํ ๋ฐ ๊ทธ reward๋ค์ ๊ธฐ์ตํด๋์๋ค๊ฐ St๊ฐ ๋๋ฉด ๋ค๋์๋ณด๋ฉด์ ๊ฐ state์ value function์ ๊ณ์ฐํ๊ฒ ๋ฉ๋๋ค. ์๋ recall that the return์ด๋ผ๊ณ ๋์ด์๋๋ฐ ์ ๊ฐ ๋งํ ๊ฒ๊ณผ ๊ฐ์ ๋ง์ ๋๋ค. ์๊ฐ ์๊ฐ ๋ฐ์๋ reward๋ค์ ์๊ฐ ์์๋๋ก discount์์ผ์ sample return์ ๊ตฌํ ์ ์์ต๋๋ค.

3. First-Visit MC vs Every-Visit MC
์์์๋ ํ ์ํผ์๋๊ฐ ๋๋๋ฉด ์ด๋ป๊ฒ ํ๋ ์ง์ ๋ํด์ ๋งํ์ต๋๋ค. ํ์ง๋ง multiple episode๋ฅผ ์งํํ ๊ฒฝ์ฐ์๋ ํ episode๋ง๋ค ์ป์๋ return์ ์ด๋ป๊ฒ ๊ณ์ฐํด์ผํ ๊น์? MC์์๋ ๋จ์ํ ํ๊ท ์ ์ทจํด์ค๋๋ค. ํ episode์์ ์ด๋ค state์ ๋ํด return์ ๊ณ์ฐํด๋จ๋๋ฐ ๋ค๋ฅธ episode์์๋ ๊ทธ state๋ฅผ ์ง๋๊ฐ์ ๋ค์ ์๋ก์ด return์ ์ป์์ ๊ฒฝ์ฐ์ ๊ทธ ๋๊ฐ์ return์ ํ๊ท ์ ์ทจํด์ฃผ๋ ๊ฒ์ด๊ณ ๊ทธ return๋ค์ด ์์ด๋ฉด ์์ผ์๋ก true value function์ ๊ฐ๊น์์ง๊ฒ ๋ฉ๋๋ค.
ํ ๊ฐ์ง ๊ณ ๋ฏผํด์ผํ ์ ์ด ์์ต๋๋ค. ๋ง์ฝ์ ํ episode๋ด์์ ์ด๋ ํ state๋ฅผ ๋ ๋ฒ ๋ฐฉ๋ฌธํ๋ค๋ฉด ์ด๋ป๊ฒ ํด์ผํ ๊น์? ์ด ๋ ์ด๋ป๊ฒ ํ๋์ ๋ฐ๋ผ์ ๋ ๊ฐ์ง๋ก ๋๋๊ฒ ๋ฉ๋๋ค.
First-visit Monte-Carlo Policy evaluation
Every-visit Monte-Carlo Policy evaluation
๋ง ๊ทธ๋๋ก First-visit์ ์ฒ์ ๋ฐฉ๋ฌธํ state๋ง ์ธ์ ํ๋ ๊ฒ์ด๊ณ (๋ ๋ฒ์งธ ๊ทธ state ๋ฐฉ๋ฌธ์ ๋ํด์๋ return์ ๊ณ์ฐํ์ง ์๋) every-visit์ ๋ฐฉ๋ฌธํ ๋๋ง๋ค ๋ฐ๋ก ๋ฐ๋ก return์ ๊ณ์ฐํ๋ ๋ฐฉ๋ฒ์ ๋๋ค. ๋ ๋ฐฉ๋ฒ์ ๋ชจ๋ ๋ฌดํ๋๋ก ๊ฐ์ ๋ true value function์ผ๋ก ์๋ ดํฉ๋๋ค. ํ์ง๋ง First-visit์ด ์ข ๋ ๋๋ฆฌ ์ค๋ซ๋์ ์ฐ๊ตฌ๋์ด ์์ผ๋ฏ๋ก ์ฌ๊ธฐ์๋ First-visit MC์ ๋ํด์ ๋ค๋ฃจ๋๋ก ํ๊ฒ ์ต๋๋ค. ์๋๋ First-Visit Monte-Carlo Policy Evaluation์ ๋ํ Silver ๊ต์๋ ์์ ์ ์๋ฃ์ ๋๋ค.

4. Incremental Mean
์์ ํ๊ท ์ ์ทจํ๋ ์์ ์ข ๋ ๋ฐ์ ์์ผ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ์ต๋๋ค. ์ ํฌ๊ฐ ํ์ตํ๋ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ๊ฐ๋ฅผ ๋ชจ์๋๊ณ ํ ๋ฒ์ ํ๊ท ์ ์ทจํ๋ ๊ฒ์ด ์๋๊ณ ํ๋ ํ๋ ๋ํด๊ฐ๋ฉฐ ํ๊ท ์ ๊ณ์ฐํ๊ธฐ ๋๋ฌธ์ ์๋๊ณผ ๊ฐ์ Incremental Mean์ ์์ผ๋ก ํํํ ์ ์์ต๋๋ค.

์ด Incremental Mean์ ์์ First-visit MC์ ์ ์ฉ์ํค๋ฉด ์๋์ ๊ฐ์ต๋๋ค. ๊ฐ์ ์์ ๋ค๋ฅด๊ฒ ํํํ ๊ฒ์ ๋๋ค. ์ด ๋, ๋ถ์๋ก ๊ฐ์๋ N(St)๊ฐ ์ ์ ๋ฌดํ๋๋ก ๊ฐ๊ฒ ๋๋๋ฐ ์ด๋ฅผ ์ํ๋ก ๊ณ ์ ์์ผ๋์ผ๋ฉด ํจ๊ณผ์ ์ผ๋ก ํ๊ท ์ ์ทจํ ์ ์๊ฒ ๋ฉ๋๋ค. ๋งจ ์ฒ์ ์ ๋ณด๋ค์ ๋ํด์ ๊ฐ์ค์น๋ฅผ ๋ ์ฃผ๋ ํํ๋ผ๊ณ ๋ณด์๋ฉด ๋ ๊ฒ ๊ฐ์ต๋๋ค. (Complementary filter์ ๋ํด์ ์์๋ ๋ถ์ ์ดํด๊ฐ ์ฌ์ธ ๊ฒ ๊ฐ์ต๋๋ค) ์ด์ ๊ฐ์ด ํ๋ ์ด์ ๋ ๊ฐํํ์ต์ด stationary problem์ด ์๋๊ธฐ ๋๋ฌธ์ ๋๋ค. ๋งค episode๋ง๋ค ์๋ก์ด policy๋ฅผ ์ฌ์ฉํ๊ธฐ ๋๋ฌธ์(์์ง policy์ update์ ๋ํด์๋ ์ด์ผ๊ธฐํ์ง ์์์ต๋๋ค) non-stationary problem์ด๋ฏ๋ก updateํ๋ ์์๋ฅผ ์ผ์ ํ๊ฒ ๊ณ ์ ํ๋ ๊ฒ์ ๋๋ค.

5. Backup Diagram
์ด๋ฌํ MC์ backup๊ณผ์ ์ ๊ทธ๋ฆผ์ผ๋ก ๋ํ๋ด๋ฉด ์๋๊ณผ ๊ฐ์ต๋๋ค.

DP์ backup diagram์์๋ one step๋ง ํ์ํ ๊ฒ์ ๋นํด์ MC์์๋ terminal state๊น์ง ์ญ ์ด์ด์ง๋๋ค. ๋ํ DP์์๋ one-step backup์์ ๊ทธ ๋ค์์ผ๋ก ๊ฐ๋ฅํ ๋ชจ๋ state๋ค๋ก ๊ฐ์ง๊ฐ ๋ป์์๋๋ฐ MC์์๋ sampling์ ํ๊ธฐ ๋๋ฌธ์ ํ๋์ ๊ฐ์ง๋ก terminal state๊น์ง ๊ฐ๊ฒ๋ฉ๋๋ค.
Monte-Carlo๋ ์ฒ์์ random process๋ฅผ ํฌํจํ ๋ฐฉ๋ฒ์ด๋ผ๊ณ ๋งํ์๋๋ฐ episode๋ง๋ค updateํ๊ธฐ ๋๋ฌธ์ ์ฒ์ ์์์ด ์ด๋์๋์ ๋ฐ๋ผ์ ๋ํ ๊ฐ์ state์์ ์ผ์ชฝ์ผ๋ก ๊ฐ๋, ์ค๋ฅธ ์ชฝ์ผ๋ก ๊ฐ๋์ ๋ฐ๋ผ์ ์ ํ ๋ค๋ฅธ experience๊ฐ ๋ฉ๋๋ค. ์ด๋ฌํ randomํ ์์๋ฅผ ํฌํจํ๊ณ ์์ด์ MC๋ variance๊ฐ ๋์ต๋๋ค. ๋์ ์ random์ธ๋งํผ ์ด๋๊ฐ์ ์น์ฐ์น๋ ๊ฒฝํฅ์ ์ ์ด์ bias๋ ๋ฎ์ ํธ์ ๋๋ค.
6. Example
Silver๊ต์๋ ๊ฐ์์์๋ Blackjack ๊ฒ์์ Monte-Carlo policy evaluation์ ์์ ๋ก ์ค๋ช ํฉ๋๋ค. ์ ์๊ฒ๋ ๋ธ๋์ญ ์์ฒด์ ๋ฃฐ์ ๋ชฐ๋ผ์ ์ด ์์ ๊ฐ ์ด๋ ต๊ฒ ๋ค๊ฐ์๊ธฐ ๋๋ฌธ์ ์์ ์์ฒด์ ๋ํด์๋ ์ค๋ช ํ์ง ์๊ฒ ์ต๋๋ค. ๊ฒ์์ ์ค์ ์ ์๋์ ๊ฐ์ต๋๋ค.

์ด์ ๊ฐ์ ๊ฒ์์์ policy๋ฅผ ์ ํด๋๊ณ ๊ณ์ computer๋ก ์๋ฎฌ๋ ์ด์ ์ ๋๋ฆฌ๋ฉด์ ์ป์ reward๋ค๋ก sample return์ ๊ตฌํ๊ณ ๊ทธ return๋ค์ incrementally mean์ ์ทจํ๋ฉด ์๋๊ณผ ๊ฐ์ ๊ทธ๋ํ๋ก ํํํ ์ ์์ต๋๋ค.

Ace์ ์ค์ ์ ๋ฐ๋ผ์ ์ ์๋๋ก ๋๋๋ ๋ฐ ์์ ๋ ๊ฐ์ ๊ทธ๋ํ๋ง ๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค. policy๋ ๊ทธ๋ํ ์๋์ ์ค์ ๋์ด ์์ต๋๋ค. state๋ x,y 2์ฐจ์์ผ๋ก ํํ๋๋ฉฐ z์ถ์ ๊ฐ state์ value function์ด ๋ฉ๋๋ค. episode๋ฅผ ์ง๋จ์ ๋ฐ๋ผ ์ ์ฐจ ์ด๋ ํ ๋ชจ์์ผ๋ก ์๋ ดํ๋ ๊ฒ์ ๋ณผ ์ ์์ต๋๋ค. 500,000๋ฒ์ฏค ๊ฒ์์ playํ์ ๊ฒฝ์ฐ์ ๊ฑฐ์ ์๋ ดํ ๊ฒ์ ๋ณผ ์ ์์ต๋๋ค. ์์ผ๋ก ํ Control์์๋ ์ด value function์ ํ ๋๋ก policy๋ฅผ updateํ๊ฒ ๋ฉ๋๋ค. ๊ทธ๋์ ์ด๋ค ๊ฒ์ด ์ข์ policy์ธ์ง ๋น๊ต๊ฐ ๊ฐ๋ฅํด์ง๋๋ค.
Last updated
Was this helpful?