[강화학습] 다중 선택

4 minute read

이번 장에서는 다중 선택 문제를 해결하기 위해 exploration - exploitation trade-off를 다루기 위한 간단한 방법들을 설명함.

210705 수정 : 이번 장에서 다루는 다중 선택 테스트는 reward가 stationary한 경우를 다루고, 이 다음장에서 finite Markov decision process부터 재미있는 예시들이

다중 선택 문제 소개

\[q_{*}(a) = E[R_{t} | A_{t} =a]\]

활용은 t 시점까지 추정한 가치에 기반해 가치가 가장 높은 행동을 취하는 탐욕적(greedy)인 행동을 의미
- 활용만 한다면 더 높은 보상을 기대할 수 있는 행동을 취하지 않아 장기적인 관점에서 바람직하다고 볼 수 없음
탐험은 탐욕적인 행동이 아닌 다른 행동을 취하는 것을 의미함.
탐험을 하는 동안 단기적으로 보상이 낮을 수 있고, 활용을 하는 동안 더 높은 보상을 줄 것으로 기대되는 행동을 하지 않기 때문에 둘 사이에 trade-off가 존재
이번 장을 통해 탐험과 활용을 적절히 분배하는 간단한 방법들을 소개함

\[Q_{t}(a)=\dfrac{\sum^{t-1}_{i=1}R_{i}\ I(A_{i}=a)}{\sum^{t-1}_{i = 1}I(A_i = a)}\]

정상(stationary) 다중 문제에 대해서는 앞의 방법이 적절하지만, 보상이 시간에 따라 변하는 비정상(non-stationary)적인 경우에는 문제가 발생함
이런 경우 최근의 보상일수록 큰 가중치를 주는 것이 타당함
time step을 0과 1 사이의 상수로 고정시키는 것이 한가지 방법
$Q_{n+1} = Q_{n} + \alpha [R_{n} - Q_{n}]$으로 놓으면 앞과 비슷한 방식으로
\[Q_{n+1} = \frac{1}{a_n}\sum^{n}_{i=1}R_i \\ = aR_{n} + Q_{n} -aQ_{n}\\ = aR_{n} + (1-a)Q_{n}\\ = aR_{n} + [(1-a)aR_{n-1} + (1-a)]\\ = aR_{n} + aR_{n} + (1-a)aR_{n-1} + (1-a)^{2}aR_{n-2} + \cdots+(1-a)^{n-1}aR_{1} + (1-a)^{n}Q_1\\ = (1-a)^{n} Q_{1} + \sum^{n}_{i=1}a(1-a)^{n-i}R_{i}\]
식을 살펴보면 초기 추정치 $Q_{1}$과 각 시점의 보상들은 한 시점이 지남에 따라 (1-a)만큼 감쇄된 값으로, i 시점의 보상은 n 시점까지 남은 time step(n-i)만큼 감쇄되어 n+1 시점에 반영됨.
$\alpha$는 감소율의 의미를 갖는다.

앞에서 고정된 $\alpha$가 아니라 time step에 따라 변화하도록 정의할 수 있는데, 추정치가 반드시 참값에 수렴하는 time step의 조건은 $\sum^{\infin}_{n=1}a_{n} = \infin,\ \ \sum^{\infin}_{n=1}a_{n}^2 < \infin$
표본 평균 방법의 경우에는 수렴 조건을 만족하지만, 최신 가중평균은 만족하지 않음
위의 조건은 정상 상태의 보상 분포를 가정할 때는 맞추어주는 것이 좋지만, 대부분의 강화학습의 문제는 비정상 상태의 보상 분포를 갖기 때문에 위 조건을 만족하는 추정 방법은 잘 사용하지 않음
- 늦은 수렴 속도
- 튜닝의 어려움 등의 문제가 있음
앞서 언급한 방법들은 모두 초기 가치 평가의 영향을 받음
- 이 점을 활용해 prior knowledge를 반영할 수 있는 점은 장점