강화학습 sutton ch2 Multi-armed Bandit] #3

Incremental Implementation

저번 시간에는 행동 가치를 추측하고 가치를 통해 행동을 선택하는 방법에 대해 얘기했다. 행동 가치를 추측하는 방법으로 sample-average을 사용하는 데, 행동할 때마다 일일이 이전의 모든 보상을 가져오는 것은 비효율적(메모리나 계산 효율 등)이다. 따라서 이를 약간 변형할 것이다. k번까지 보상을 받았다고 하면 추측한 k+1번째 $Q_{k+1}$은 다음과 같다.

$k=1$이라면, $Q_2=R_1$이 된다. 이전 sample-average와 달리 오로지 $Q_k$와 $k$만 있으면 되기에 계산량이 적다. 위 식을 일반적인 식으로 다음과 같이 나타낼 수 있다.

[Target - OldEstimate]는 추측(estimate)에서 error이다. Target($R_k$)과 error만큼 차이나서 그 만큼 변하면 Target 값이 될 것이다.

그리고 $StepSize$가 있다. 위 식에서는 $\frac{1}{k}$으로 간단히 $\alpha$로 표현해 $\alpha = \frac{1}{k}$으로 나타낼 것이다.

Tracking a Nonstationary Problem

sample-average 방법은 변하지 않는 환경(stationary environment)일 때만 좋다. 강화학습 문제에서는 보통 시간에 따라 환경이 변한다.(nonstationary) 그럼 변했다고 했을 때, 과거에 받았던 보상보다는 현재 당장 받은 보상이 중요하다. 그렇기에 현재 받은 보상에 좀 더 치중하고 싶은데, 좋은 방법 중에 하나가 step-size를 고정하여 사용하는 것이다. 이전에 $Q_t$를 업데이트 하는 식을 다시 보자.

여기서 $\alpha = \frac{1}{k}$이였으나 $\alpha \in (0, 1]$($0< \alpha \le 1$)인 상수로 사용하는 것이다. 그럼 이 식을 다시 풀어서 보면,

$R_k$가 최근 보상, $R_1$이 가장 이전의 보상인데, $(1-\alpha)^{k-1}\alpha$만큼 곱한다는 것을 볼 수 있다. $1-\alpha$는 0과 1사이의 값이므로($\alpha \in (0, 1]$)이를 제곱할 수록 더 많이 작아진다. 따라서 결과적으로 $R_1$보다 $R_k$에 더 치중한 것을 알 수 있다.

이를 weighted average라 부른다. 왜냐하면 weight들의 합은 $(1-\alpha)^k + \sum^k_{i=1} \alpha(1-\alpha)^{k-i}=1$이기 때문이다.

Optimistic initial values

$\alpha$에 따라 이전으로 갈수록 이전 보상들을 exponentially 작게 만든다.(weight decay) $\alpha$가 클 수록 현재 보상에 좀 더 집중한다는 뜻으로 만약 $\alpha=1$($1-\alpha= 0$)이라면 오로지 현재 보상($R_t$)만 가치로 판단한다. 그래서 이를 exponential, recency-weighted average라고 부르기도 한다.

참고

$\alpha$를 step 때마다 다르게 두는게 좋을 수도 있다. 그래서 k번째 행동 a에 대한 step-size를 $\alpha_k(a)$라 정의하고, $\alpha$의 선택에 따라 stochastic approximation 이론에서는 확률 1로 수렴하게 하는 $\alpha$ 조건을 다음과 같이 낸다.
$$ \sum^\infty_{k=1} \alpha_k(a) = \infty$$
$$ and $$
$$ \sum^\infty_{k=1} \alpha_k^2(a) < \infty $$
첫 번째 조건은 초기 조건이나 임의의 변함에도 잘 견뎌낼 정도로 커야한다는 뜻이고, 두번 째는 수렴하기 위해 충분히 작아야한다는 뜻이다.(..?)
$\frac{1}{k}$는 만족하지만 상수 $\alpha$는 만족하지 않는다. 이 말이 무슨말인가?라면 true value에 수렴하지 못한다는 얘기이다. 하지만 nonstationary environment에서는 필요하다. 강화학습에서는 nonstationary environment가 흔하기 때문에 어쩔 수가 없는 것 같다.

다음 시간에는

실제 강화학습 알고리즘에서는 잘 다루지는 않아서 깊이 들어가야하나 고민이지만 초기값과 Upper-Confidence-Bound Action에 대해 다룰 예정이다. 사실 기초는 $\alpha$의 존재정도 까지만 알아도 상관없을 듯.

Reference

Reinforcement Learning: An Introduction