๐ก TIL/Algorithm
Multi-Armed Bandits(MAB) ์๊ณ ๋ฆฌ์ฆ
0. Multi-Armed Bandits(๋ฉํฐ์๋ ๋ฐด๋ง) ์ ์ญ์ฌ ์นด์ง๋ ธ์ ๊ณ ๊ฐ๋ค์ ํน์ ์ฌ๋กฏ๋จธ์ ์ ์์ต๋ฅ ์ด ์ข๋ค๋ ์ฌ์ค์ ๊ฒฝํ์ ์ผ๋ก ์๊ฒ๋๋ค. ๋, ํ๋ฒ ๋๋ฐ์ด ํฐ์ง ์ฌ๋กฏ๋จธ์ ์ ํ๋์ ์์ต๋ฅ ์ด ์ข์ง ์๋ค๋ ์ฌ์ค์ ์๊ฒ๋๋ค. ์ด๋๋ , ์นด์ง๋ ธ์ ๋ฐฉ๋ฌธํ ์ํ์๊ฐ “์ด ์ฌ๋กฏ๋จธ์ ์ ์ด๋ป๊ฒ ํฌ์๋ฅผ ํ๋ฉด ์ต์ ์ ์์ต์ ์ป์ ์ ์์๊น?” ๋ผ๋ ์๊ฐ์ ํ๊ฒ ๋๋ค. ๐ก ๋ฉํฐ ์๋ ๋ฐด๋ง์ ์นด์ง๋ ธ์์ ์ฌ๋กฏ๋จธ์ ํฌ์๋ฅผ ์ต์ ํํ๊ธฐ ์ํด ๋ง๋ค์ด์ง ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์ ๋ฆฌํ์๋ฉด, N๊ฐ์ ์ฌ๋กฏ๋จธ์ ์ด ์๋ค. ๊ฐ๊ฐ์ ์ฌ๋กฏ๋จธ์ ์ ์์ต๋ฅ ์ด ๋ค๋ฅด๋ค. ๋น์ฅ, ๊ณ ๊ฐ์ ๊ฐ ์ฌ๋กฏ๋จธ์ ์ ์์ต๋ฅ ์ ์์ง ๋ชปํ๋ค. ์ฌ๊ธฐ์ ๋ด ๋์ ์ด๋ ์ฌ๋กฏ๋จธ์ ์ ๊ฑธ๊ณ ์ฌ๋กฏ๋จธ์ ์ ์(์์ก์ด)์ ๋ด๋ ค์ผ ๋์ ๊ฐ์ฅ ๋ง์ด ๋ฒ ์ ์์๊น? ์ฌ๊ธฐ์ ์ฌ๋กฏ๋จธ์ ์ด ๋ฐด๋ง(Bandit)์ด๊ณ , ..
์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ
โ 2022.02.01 ๊ธฐ์ค ๋ด์ฉ ์ถ๊ฐ์ค ๊ธฐ๋ณธ ์๊ฐ ๋ณต์ก๋ ์ ๋ ฅ๊ฐ๊ณผ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ํจ์ ๊ด๊ณ๋ก ๋ํ๋ธ ๊ฒ ์ฆ ์คํ์๊ฐ์ ๊ธฐ์ค์ผ๋ก, ์๊ณ ๋ฆฌ์ฆ์ด ์ผ๋ง๋ ํจ์จ์ ์ธ์ง๋ฅผ ํ๋จํ ์ ์๋ ์ฒ๋ ์๊ฐ ๋ณต์ก๋๋ ์ต์ ์ ๊ฒฝ์ฐ, ์ต์ ์ ๊ฒฝ์ฐ, ํ๊ท ์ ๊ฒฝ์ฐ๋ฅผ ๊ณ์ฐ ์ด๋ ์ต์ ์ ๊ฒฝ์ฐ๋ Big-O, ์ต์ ์ ๊ฒฝ์ฐ๋ Big-Ω, ํ๊ท ์ ๊ฒฝ์ฐ๋ Big-θ๋ก ๋ํ๋ธ๋ค. Big O ์ต์ ์ ๊ฒฝ์ฐ ์๊ณ ๋ฆฌ์ฆ์ ์คํ์์ผฐ์ ๋, ์ต๋๋ก ๊ฑธ๋ฆด ์ ์๋ ์๊ฐ(์ํ ์๊ฐ) ์๋ฏธ n์ด ๋ฌดํ๋๋ก ๊ฐ๋ค๊ณ ํ์ ๋ ์์ํญ์ ์ ๊ฑฐํ n์ผ๋ก ๋ณต์ก๋๋ฅผ ํํํ๋ ๋ฐฉ์ ๊ฐ์ฅ ๋ณดํธ์ ์ธ ๋ฐฉ๋ฒ "๋๊ฐ ์ง๊ธ ์ค๊ณํ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ๋ณต์ก๋๊ฐ ์ผ๋ง์ฏค ๋๋?" ๋ผ๊ณ ํ๋ฉด "O(n logn)์ ๋ ๋จ " Big-Omega ์ต์ ์ ๊ฒฝ์ฐ ์๊ณ ๋ฆฌ์ฆ์ ์คํ์์ผฐ์ ๋, ์ต..
์๊ณ ๋ฆฌ์ฆ ๊ณต๋ถ ์์ ๋ฐฉ๋ฒ ๋ฐ ์์
Yena Choi ๋์ ์๊ณ ๋ฆฌ์ฆ ๊ณต๋ถ ์์ ๋ฐฉ๋ฒ ๋ฐ ์์ ๋ฅผ ์ฝ๊ณ ์ ๋ฆฌํ ๋ด์ฉ์ ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ด๋? ์ด๋ ํ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ์ผ๋ จ์ ์ ์ฐจ๋ฅผ ๊ณต์ํํ ํํ๋ก ํํํ ๊ฒ. ์๊ณ ๋ฆฌ์ฆ์ ์กฐ๊ฑด ์ข์ ์๊ณ ๋ฆฌ์ฆ์ ๋ง๋ค๊ธฐ ์ํด์๋ ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ ์ถฉ์กฑ์์ผ์ผ ํ๋ค. ์ ๋ ฅ : ์ธ๋ถ์์ ์ ๊ณต๋๋ ์๋ฃ๊ฐ 0๊ฐ ์ด์ ์กด์ฌํ๋ค. ์ถ๋ ฅ : ์ ์ด๋ 2๊ฐ ์ด์์ ์๋ก ๋ค๋ฅธ ๊ฒฐ๊ณผ๋ฅผ ๋ด์ด์ผ ํ๋ค. ์ฆ ๋ชจ๋ ์ ๋ ฅ์ ํ๋์ ์ถ๋ ฅ- ์ด ๋์ค๋ฉด ์ ๋๋ค. ๋ช ํ์ฑ : ์ํ ๊ณผ์ ์ ๋ช ํํ๊ณ ๋ชจํธํ์ง ์์ ๋ช ๋ น์ด๋ก ๊ตฌ์ฑ๋์ด์ผ ํ๋ค. ์ ํ์ฑ : ์ ํ ๋ฒ์ ๋ช ๋ น์ด๋ฅผ ์ํ ํ ์ ํ ์๊ฐ ๋ด์ ์ข ๋ฃํ๋ค. ํจ์จ์ฑ : ๋ชจ๋ ๊ณผ์ ์ ๋ช ๋ฐฑํ๊ฒ ์คํ ๊ฐ๋ฅ(๊ฒ์ฆ ๊ฐ๋ฅ)ํ ๊ฒ์ด์ด์ผ ํ๋ค ๊ณต๋ถ ์์ ๊ธฐ๋ณธ ๊ฐ๋ ์ดํด ๊ธฐ๋ณธ ์๊ณ ๋ฆฌ์ฆ ์ฝ๋ ํ์ต ์ฌ์ด ๋ฌธ์ ํ๊ธฐ … (์ด..