Multi-Armed Bandit for RL(3) - Gradient Bandit Algorithms

이번 포스팅에서는 Gradient Bandit Algorithms에 대해 알아보겠습니다. 내용은 심플한데 업데이트 알고리즘을 유도하는 과정이 조금 복잡합니다. 유도하는 과정을 이해하지 않더라도 충분히 적용가능하니 유도하는 내용은 취사적으로 읽어보면 좋을 것 같습니다.

Gradient Bandit Algorithm

MAB(2)에서는 action value 이용한 행동 선택 전략을 알아봤습니다. 물론 좋은 방법이지만 당연히 action value가 아닌 다른 방법으로도 행동 선택 전략을 수립할 수 있습니다. 또 다른 대표적인 행동 선택 전략은 선호도(preference)를 이용하는 gradient bandit algorithm입니다. $H_{t}(a)$를 $t$ 시점에서 행동 $a$의 선호도로 정의하겠습니다. 처음에는 임의의 값으로 초기화를 하고 뒤따를 알고리즘을 이용하여 선호도를 학습합니다. Gradiet Bandit Algorithm에서는 선호도를 직접이용하지 않고, softmax 함수에 적용하여 확률처럼 선호도를 재표현합니다. $$\mathbb{P}\left(A_{t}=a\right)=\frac{e^{H_{t}(a)}}{\sum_{b=1}^{k}e^{H_{t}(b)}}=\pi_{t}(a)$$ 여기에서 $\pi_{t}(a)$라는 중요한 새로운 notation이 등장하며, 이는 강화학습을 공부하며 앞으로도 자주 등장하니 꼭 눈여겨두면 좋습니다. 아까 선호도를 확률처럼 재표현 한다고 했고, $\pi_{t}(a)$는 $t$시점에서 행동 $a$를 선택할 확률로 해석하면됩니다. 행동 선택 확률은 매 시점마다 gradient ascent method로 업데이트 할 수 있고, 그래서 이름이 gradient bandit algorithm입니다. $$\begin{align*}H_{t+1}(A_{t})&\leftarrow H_{t}(A_{t})+\alpha\left(R_{t}-\bar{R}_{t}\right)\left(1-\pi_{t}A_{t}\right)\text{, and}\\H_{t+1}(A_{t})&\leftarrow H_{t}(a)-\alpha\left(R_{t}-\bar{R}_{t}\right)\pi_{t}(a)\text{, for all }a\ne A_{t}\end{align*}$$ 여기에서 $\alpha>0$은 step size parameter로 사용자가 지정해주면 되고, $\bar{R}_{t}\in\mathbb{R}$은 $t$시점을 포함한 보상의 평균이고 baseline 역할을 합니다. 위 알고리즘은 $R_{t}$가 baseline보다 큰 행동을 했을 경우 선호도를 증가시키고 아닌경우 감소하며 업데이트를 한다고 해석 할 수 있습니다. 이어서 어떻게 유도가 되었는지 확인하겠습니다. (실제 적용할 때는 위 내용으로 충분하니 취사적으로 읽어보면 좋을 것 같습니다:))

Gradient Bandit Algorithm 유도

Gradient Ascent Method

Gradient Ascent Method는 단순히 Descent Method와 기울기 방향의 차이만 있을 뿐, 나머진 같습니다. 자세한 설명은 이곳에서 확인하시면 됩니다. $$x^{(k+1)}\leftarrow x^{(k)}+\alpha\frac{\partial f(x^{(k)})}{\partial x^{(k)}}$$

Gradient Bandit Algorithm

Action Value Method에서는 기대보상을 단순히 가중평균을 이용하여 산출했습니다. Gradient Bandit Algorithm은 확률 기반 행동 선택을 하기 때문에 매 시점에서 기대보상을 다음과 같이 계산할 수 있습니다. $$\mathbb{E}R_{t}=\sum_{x}\pi_{t}(x)q_{*}(x)$$ 위 식에서 $\mathbb{E}R_{t}$가 선호도 $H_{t}(x)$의 함수임을 쉽게 알 수 있고 자연스럽게 gradient ascent method가 적용가능하다는 사실도 알 수 있습니다. 따라서 기대보상을 최대화하는 선호도는 다음과 같이 업데이트 할 수 있습니다. $$H_{t+1}(a)=H_{t}(a)+\alpha\frac{\partial \mathbb{E}R_{t}}{\partial H_{t}(a)}$$ 갑자기 등장한 $q_{*}(a)$가 조금 의아할 수 있지만, 이 부분은 유도 말미에 해결책이 있으니 우선은 받아드리고 기울기를 구해보겠습니다. $$\begin{align*}\frac{\partial\mathbb{E}R_{t}}{\partial H_{t}(a)}&=\frac{\partial}{\partial H_{t}(a)}\left[\sum_{x}\pi_{t}(x)q_{*}(x)\right]\\&=\sum_{x}q_{*}(x)\frac{\partial \pi_{t}(x)}{\partial H_{t}(a)}=\sum_{x}\left(q_{*}(x)-B_{t}\right)\frac{\partial\pi_{t}(x)}{\partial H_{t}(a)}\end{align*}$$ 여기서 $B_{t}$는 baseline이고 $x$에 의존하지 않는 어떤 scalar가 들어와도 상관이 없습니다. $\left(\because \sum_{x}\frac{\partial\pi_{t}(x)}{\partial H_{t}(a)}=\frac{\partial}{\partial H_{t}(a)}\sum_{x}\pi_{t}(x)=0\right)$ $\pi_{t}(x)/\pi_{t}(x)$를 곱해주면, $$\begin{align*}\frac{\partial \mathbb{E}R_{t}}{\partial H_{t}(a)}&=\sum_{x}\pi_{t}(x)\left(q_{*}(x)-B_{t}\right)\frac{\partial \pi_{t}(x)}{\partial H_{t}(a)}/\pi_{t}(x)\\&=\mathbb{E}\left[\left(q_{*}(A_{t})-B_{t}\right)\frac{\partial \pi_{t}(A_{t})}{\partial H_{t}(a)}/\pi_{t}(A_{t})\right]\\&=\mathbb{E}\left[\left(q_{*}(A_{t})-B_{t}\right)\left(I_{a=A_{t}}-\pi_{t}(a)\right)\right]\\&=\mathbb{E}\left[\left(\mathbb{E}(R_{t}|A_{t})-\bar{R}_{t}\right)\left(I_{a=A_{t}}-\pi_{t}(a)\right)\right]\end{align*}$$ 여기까지 진행할 수 있습니다. 먼저 앞서 말한 조건에 따라 $B_{t}=\bar{R}_{t}$로 바꿔쓸 수 있습니다. 또한 $\frac{\partial\pi_{t}(x)}{\partial H_{t}(a)}=\pi_{t}(x)\left(I_{a=x}-\pi_{t}(a)\right)$이기 때문입니다. 마지막으로 조금 기술적인 이야기를 하면 목적지에 도착합니다. 우리는 1회 실행 후 1회 업데이트를 진행하기 때문에 $\mathbb{E}$(기대값)을 계산(추정)할 때 표본의 크기가 항상 1개 입니다. 따라서 바로 직전 $\mathbb{E}$(기대값) 안의 값을 그대로 사용하는 것과 마찬가지 결과를 얻습니다. 마무리짓도록 하겠습니다. $$H_{t+1}(a)=H_{t}(a)+\alpha(R_{t}-\bar{R}_{t})(I_{a=A_{t}}-\pi_{t}(a))\text{, }\forall a$$

마치며

이 번 포스팅까지 MAB의 기본적인 내용을 다루었습니다. 고생하셨습니다. 끝까지 읽어주셔서 진심으로 감사합니다! :)

References

• Sutton, Richard S., and Andrew G. Barto. Introduction to reinforcement learning. Vol. 2. No. 4. Cambridge: MIT press, 1998.