5 분 소요

글에 들어가기 앞서…

이 포스팅은 ‘강화학습‘에 대한 내용을 담고 있습니다.

자료 출처: 단단한 강화학습, Reinforcement Learning An Introduction , 2nd edition. 리처드 서튼, 앤드류 바트로, 김성우(옮긴이)

다중 선택

이 포스팅에서 다루는 내용은 다중 선택입니다. 그 중에서도 비연합 다중 선택을 다루는데요, 비연합 다중선택의 의미를 알기 위해서는 비연합이 무슨 의미인지, 그리고 무엇을 선택하는지를 명확히 할 필요가 있습니다.

  • 비연합: 현재 시각에서 가능한 행동들 중에 선택을 할 때, 상태 정보를 무시해도 무방한 문제를 의미합니다.
  • 무엇을 선택하는가?: 학습자가 선택하는 것은 행동(Action)입니다. 학습자는 선택 과정에서 계산상에 있어서 상태 정보가 필수적이지는 않기 때문에 이를 활용할 수도 있고, 활용하지 않을 수도 있습니다. 활용하지 않고 풀어도 되는 경우를 비연합 다중 선택 문제(Nonassociative k-armed bandit problem)라고 하고, 상태 정보를 활용해 풀어야 하는 문제를 연합 다중 선택 문제(Associative k-armed bandit problem)라고 합니다.

이 포스팅에서 다룰 내용은 비연합 다중 선택 문제에 관한 것이지만, 사실 강화학습 문제는 비연합 다중 선택 문제도, 연합 다중 선택 문제도 아닙니다. 강화학습 문제가 되기 위해서는 예전의 선택이 몇 스텝 이후의 결과에도 영향을 미쳐야 합니다. 반면, 다중 선택 문제는 단발성으로 끝나는, 즉, 하나의 시간 스텝만으로 결정되기 때문에 강화학습 문제라고 보기 어렵습니다. 그렇지만 다중 선택 문제 사용되는 다양한 기본적인 학습 방법들이 강화학습 문제를 풀 때에도 사용되기 때문에, 다중 선택 문제라는 간단한 경우에서 어떻게 그런 기본적인 방법들이 사용되는지 잘 알 필요가 있습니다.

행동 가치 방법

행동의 가치를 추정하고 추정값으로부터 행동을 선택하도록 결정하는 방식을 총칭해 행동 가치 방법(Action-Value Method)이라고 합니다. 이전 포스트의 가치 함수에서는 상태(State)의 가치를 추정했는데요, 행동 가치 방법에서는 행동의 가치를 추정하기 위한 가치 함수를 사용합니다.

\[Q_t(a) \doteq \frac{\sum_{i=1}^{t-1}R_i\cdot \mathbb{1}_{A_i = a}}{\sum_{i=1}^{t-1}\mathbb{1}_{A_i = a}}\]

위 식은 행동의 가치를 추정하는 행동 가치 함수의 정의를 나타낸 것인데요, 식을 통해 알 수 있는 점은 표본평균을 추정값으로 사용하고 있다는 사실입니다. 이런 방식으로 행동 가치 함수를 추정하는 방법을 표본평균 방법이라고 합니다. 표본평균 방법은 행동 가치 함수를 추정하는 다양한 방법 중에 하나일 뿐, 반드시 최선의 방법인 것은 아닙니다.

행동 가치 함수가 어느정도 쌓이면, 이 함수를 기반으로 행동을 수행할 규칙인 정책(Policy)의 종류를 결정해야 합니다. 선택할 수 있는 가장 기본적인 규칙은 가장 가치가 높은 행동을 선택하는 탐욕적(Greedy) 행동 선택 방법입니다.

\[A_i \doteq \underset{a}{argmax}Q_t(a)\]

탐욕적 행동 선택 방법을 따르게 되면, 탐색은 더 이상 발생하지 않습니다. 탐색은 학습자에게 있어 더 큰 보상을 받을 수 있는 가능성을 주기 때문에 필수적인데요, 이를 위해서 활용에 비해 상대적으로 작은 가능성인 $\epsilon$만큼의 탐색이 고정적으로 일어나게 하는 방법을 사용합니다. 이 방식을 입실론 탐욕적 방법($\epsilon$-greedy)이라고 합니다.

보상이 결정론적(deterministic)으로 주어지는, 그리고 정상적인(Stationnary) 다중 선택 환경에서는 최상의 성능을 보여줍니다. 왜냐하면, 곧바로 최적 행동을 찾아내고 다시는 탐험을 하지 않기 때문입니다. 하지만, 둘 중 하나라도 아닌 경우에는 입실론 탐욕적 방법이 더 우수한 성능을 보여줍니다. 이는 보상에 포함된 불확실성의 수준에 기인하는데요(탐색의 중요성이 상승), 그 수준이 높아지면 높아질수록 입실론 탐욕적 방법이 상대적으로 강한 모습을 보입니다.

점증적 구현

표본평균 방식으로 특정 행동의 가치를 추정하기 위해서는 모든 보상을 기록해 두어야 합니다. 사실 이 과정이 정말 필수적인 것은 아닌데요, 새롭게 추가된 보상의 관측값과 기존 보상의 평균값을 알고 있으면 새로운, 업데이트 된 가치 함수 값을 구할 수 있습니다.

\[Q_{n+1} = Q_n + \frac{1}{n}[R_n - Q_n]\]

위의 식을 사용하면 이전의 모든 보상들을 기록할 필요가 없어집니다. 이제 이 모든 사실들을 사용해서 알고리즘을 만들면 아래와 같겠습니다.

a = 1, ..., k에 대해서 초기화

Q(a) <- 0
N(a) <- 0

while True:
	k = random(0, 1)
	if k <= epsilon:
		A = random action 
	else:
		A = argmax(Q(a))
		
	R <- bandit(A); 행동에 대한 이득을 계산하는 함수
	N(A) <- N(A) + 1
	Q(A) <- Q(A) + (1/N(A))*(R - Q(A))

비정상 문제

위에서 다루었던 표본평균 방식과 점증적 구현은 모두 정상 다중 선택 문제에 적합한 해결방식입니다. 문제 상황이 비정상적이라면 위의 알고리즘은 적절하지 않을 가능성이 높습니다. 보상의 분포가 계속 변화하는 경우에는 최근의 보상에 더 큰 가중치를 주고 오래된 보상일수록 낮은 가중치를 주는 것이 타당합니다. 점증적 갱신 규칙을 조금만 수정하면, 이런 비정상문제에 적절히 대응하는 학습자를 만들 수 있습니다.

\[Q_{n+1} = Q_n + \alpha[R_n - Q_n]\]

점증적 갱신 방식과 달리 시간 간격 파라미터를 상수로 고정하면, 오래된 보상일수록 기하급수적으로 가중치가 줄어들게됩니다. 이것을 기하급수적 최신 가중 평균(Exponential Recency-Weighted Average)라고 합니다.

시간 간격 파라미터는 필요에 따라 다양하게 설정될 수 있습니다. 하지만 수렴성을 보장하기 위해서는 확률론적 근사 이론에 따라 밝혀진 아래의 두 조건을 만족해야 합니다.

\[\sum_{n=1}^{\infty}\alpha_n(a) = \infty\] \[\sum_{n=1}^{\infty}\alpha_n^2(a) \lt \infty\]

위 식에 따르면 표본평균 방식은 두 조건을 만족하기 때문에 수렴성을 만족합니다. 반면, 시간 간격 파라미터를 상수로 두는 경우는 두 번째 조건을 만족하지 못하기 때문에 수렴성을 만족하지 못합니다.

긍정적 초깃값

탐욕적 행동 선택 방법을 살펴보다 보면 걱정이 되는 부분이 한 가지 있는데요, 가치 함수의 초깃값이 0으로 설정되는 경우에, 만약 첫 번째 선택에서 양수 보상을 받는다면, 더 이상 어떤 다른 행동을 선택하지 않을지도 모른다는 점입니다. 실제로 그렇습니다. 탐욕적 행동 선택 방법 뿐만이 아니라 위에서 살펴 본 모든 방법은 행동 가치의 초기 추정값에 어느 정도의 영향을 받습니다.

탐욕적 행동 선택 방법을 채택하는 학습자에게 탐색을 강요하는 방법 중 하나가 바로 긍정적 초깃값 설정입니다. 모든 행동에 대해 충분히 큰 양수로 초깃값을 설정한다면, 학습자는 초기에 모든 행동들에 대해 최소 한 번 이상의 탐색을 수행할 것이이고, 이를 통해 더 좋은 성능을 기대할 수 있습니다. 하지만 이 방식은 정상적인 문제에는 유용하지 모르나, 비정상적인 문제에는 도움이 되지 못합니다. 왜냐하면, 긍정적 초깃값으로 기인된 탐색 효과는 시간의 시작 지점에 국소적으로 존재하기 때문입니다.

신뢰 상한 행동 선택

신뢰 상한 행동 선택(Upper Confidence Bound/UCB)란 제곱근 항을 통해 행동의 가치에 대한 추정값의 불확실성, 편차를 고려합니다.

\[A_t \doteq \underset{a}{argmax}[Q_t(a) + c\sqrt{\frac{\ln{t}}{N_t(a)}}]\]

위의 식을 사용해 행동을 선택하면, 입실론 없이도 탐색을 수행하게 됩니다. UCB는 정상적인 문제를 잘 해결하지만, 비정상적인 문제를 다룰 때 복잡한 방식이 필요하고, 큰 상태 공간을 다루기 매우 곤란하다는 단점이 있습니다.

경사도 다중 선택 알고리즘

경사도 다중 선택 알고리즘(Gradient Bandit Algorithm)을 사용해서 다중 선택 문제를 해결할 수도 있는데요, 이 방식에서는 가치 함수를 사용하지 않는 대신 수치적 선호도를 학습합니다. 그리고 행동을 선택할 때에는 행동 선호도에 소프트맥스 분포를 취해 확률값을 뽑아내고, 이를 기반하여 행동합니다.

\[Pr\{A_t = a\} \doteq \frac{e^{H_t(a)}}{\sum_{b=1}^{k}e^{H_t(b)}} \doteq \pi_t(a)\]

정책은 위와 같이 정의됩니다. 위 식에서 가장 중요한 선호도를 업데이트하는 식을 유도하는 과정은 아래와 같습니다.

\[H_{t+1}(a) \doteq H_t(a) + \alpha \frac{\partial\mathbb{E}[R_t]}{\partial H_t(a)}\]

선호도의 업데이트 방향은 보상의 평균이 증가하는 방향이어야 합니다. 여러 유도과정을 거치면, 아래와 같은 식을 얻을 수 있습니다.

\[H_{t+1}(a) = \mathbb{E}[(R_t - \bar{R}_t)(\mathbb{1}_{a=A_t}-\pi_t(a))]\]

시간 간격 파라미터까지 포함한 최종적인 업데이트 식은 아래와 같습니다.

\[H_{t+1}(a) = H_t(a) + \alpha\mathbb(R_t - \bar{R}_t)(\mathbb{1}_{a=A_t}-\pi_t(a))\]

연관 탐색

연관 탐색(Associative Search) 문제란 상태 정보를 활용해 해결해야 하는 문제를 의미하는데요, 이 경우 상태 정보를 활용하지 않는 경우 최적의 학습자를 만드는 것은 정말 어렵습니다. 이 경우 학습자의 정책은 어떤 상황으로부터 그 상황에 맞는 최고의 행동을 도출하는 대응 관계이어야 합니다.

댓글남기기

참고