본문으로 바로가기

Optimistic Initial Values

이전까지 다룬 모든 방법(sample-average, weight average 등)은 초기에 추측한 행동 가치 $Q_1(a)$에 따라 달라진다. 통계학에서는 이를 biased(편향되었다)라고 말한다. sample-average같은 경우 모든 행동의 경우가 최소 한번 나왔다면 bias는 없지만 상수 $\alpha$ 방법은 계속 남아 있다. 이런 bias로 인해 사용자가 정해줘야 하는 부분이 되기는 하지만 원하는 수준의 보상을 얻기 위한 사전지식으로 쉽게 줄 수 있다.

또는 exploration을 하도록 만드는 효과가 있다. 저번에 10-armed testbed를 다시 떠올려보자. 만약 초기 추측값을 모두 +5로 맞추면 보상이 어떻게 나오든 5보다 작아서 하지 않은 행동들이 한 행동들의 추측값보다 무조건 높게 나온다. 그렇다면 하지 않았던 행동들을 하게 만드는, 즉, exploration 효과가 있다. 그렇다면 greedy action이라 해도 초기 estimate에 의해 무조건 하나만 택하지는 않을 것이다.

$\epsilon-greedy$보다 더 좋게 나오는 greedy-action

저번 시간 $\epsilon$-greedy action(0.1)이 greedy-action보다 좋았다. 초기값을 다르게 한 것만으로 greedy가 더 효과가 좋을 수 있음을 볼 수 있다.(초기에 exploration을 효과적으로 하기 때문에) 그런데 사실 stationary(변하지 않는) 환경에서만 좋을 뿐 일반적으로는 유용하지 않다. 계속 변하는데 이전의 값은 점점 무의미해지기 때문이다. 이는 저번에 sample-average에서 나온 문제점과 비슷하다. 이전 모든 보상의 평균이기 때문에 예전 보상이나 현재 보상이나 동등하게 보았으나, 환경이 계속 변한다면 이전 보상은 무의미하다.

이렇게 초기값을 통해 exploration을 주는 기술을 optimistic initial value라고 한다.

Upper-Confidence-Bound Action Selection

행동 가치를 추측하는 것은 불확실하기에 탐험이 필요하다. 하지만 $\epsilon$-greedy는 추측값이나 불확실성과는 상관없이 무조건 강제로 랜덤한 행동을 하게 한다. 좀 더 고려해주면 좋을텐데...라는 생각에서 나온 방법 중에 하나가 upper confidence bound (UCB)이다.

  • time step $t$
  • 행동 a를 한 횟수 $N$ (0이라면 해야할 행동으로 취급)
  • exploration 하는 정도를 조절하는 상수 $c$

루트 안에 있는 것은 불확실성 또는 행동 a에 대한 가치 추측값의 분산을 보고있는 것이다. 좀 쉽게 말하자면 어떤 행등들 해왔다고 했을 때, 그 행동은 많이 해봤으니 어느 정도 불확실하지 않을 것이다. 수식에서 본다면 $N_t(a)$값이 올라가고 그에 따라 루트 값은 낮아질 것이다. 만약 많이 안해본 행동들은 어떻게 될까? 분모 $N_t(a)$는 증가하지 않지만 분자 $ln t$는 계속 증가한다. 그렇다면 루트 값은 증가한다. 결국 행동해본 것들은 불확실성(루트값)이 낮아지고 안해본 것들은 값이 올라간다.

자연로그 $ln t$를 사용한 이유는 시간이 지날수록 증가 비율이 작아진다. 하지만 제한이 있지는 않다.(unbounded) 오랜 시간이 지나 모든 행동이 선택되고 충분히 행동해봤다면 불확실성을 나타내는 항은 더이상 큰 값을 가지고 있지 않아 해보지 않은 행동은 덜 해보게 될것이다.

10-armed testbed에서 $\epsilon$-greedy와 비교한 결과 조금 더 좋다. 하지만 여전히 $\epsilon$-greedy보다 일반적인 문제에 약하다. 그놈의 nonstationary가 문제다. 나중에는 불확실성 값은 충분히 작아져버릴텐데, 그렇게 되면 exploration을 더 이상 하지 않는다. 현재 UCB를 실제로 사용된 방법은 없는 것 같다.

다음 시간에는

이전에는 가치를 보고 그 행동을 했는데 다르게 행동을 선택하는 방법에 대해서 얘기해볼 예정이다.