Sutton Ch.01-02 Multi-armed Bandits
업데이트:
Ch.1 Introduction
우리들은 무언가를 자연스럽게 익힐 때 환경과 상호작용 합니다. 우리가 아기였을 때를 생각해보면 특별히
선생님께 배우지 않아도 주어진 환경 속에서 여러가지를 자연스럽게 배우게 되는 것을 알 수 있죠.
여기서 중요한 점은 주어진 환경과 우리 자신을 정확히 아는 것 입니다.
즉, 우리가 어떤 행동을 했을 때, 환경이 우리 행동에 어떻게 반응하는지 정확히 파악하는 것이 중요합니다.
강화학습에서는 행동에 따른 보상(reward)이 따르게 되는데, 강화학습은 다시 말해
보상을 최대화 하는 환경(environment)과 행동(action)을 맵핑한다고 생각하시면 됩니다.
강화학습의 어려운 점은 최고의 보상을 주는 행동을 찾기위해 시행착오의 과정이 길어질 수 있다는 점과
자신의 행동에 대한 보상이 즉각적으로 나타나지 않을 수 있다는 것입니다.
보통 머신러닝, 지도학습, 비지도학습, 강화학습이라는 용어에 대해 헷갈려하시는 분들을 위해 이 용어들의 차이점을 알아보고 가겠습니다.
지도학습(supervised learning)과의 차이점
지도학습은 라벨링 된(labeled) 트레이닝 셋을 이용합니다. 여기서 라벨링은
주어진 환경에 대해 취해야 할 행동이 명확하다는 뜻이라고도 생각할 수 있습니다.
지도학습은 여러 가지 문제를 해결하는데 유용하지만 환경의 변화에 적응하지 못 한다는 한계점이 있습니다.
비지도학습(unsupervised learning)과의 차이
비지도학습은 라벨링 되지 않은(unlabeled) 데이터의 숨은 구조를 찾아내는 학습법입니다. 반면 강화학습의 목표는 데이터의 숨은 구조를 찾아내는 것이 아닌, 보상을 최대화하는 행동을 찾는 것입니다. 그러므로 강화학습은 지도학습, 비지도학습과 다른 세번째 패러다임으로 생각해야 합니다.
Chapter2. Multi-armed Bandits
강화학습이 다른 머신러닝과 차별되는 점은 트레이닝 셋을 올바른 행동(action)을 주기 위함이 아니라,
행동을 평가(evaluate)하는데 사용한다는 점이다.
이는 좋은 행동을을 명백히 찾을 수 있는 활발한 exploration 니즈를 만들게 된다.
단지 그 행동이 얼마나 좋은지, 최악의 행동인지 최선의 행동인지만을 평가하는 것이 아니다.
강화학습에서의 피드백은 앞으로 어떤 행동을 취해야할지를 나타내는데, 이 때, 실제 어떤 행동을 취하는 지와는 독립적이다.
이번 챕터에서는 한 가지 상황에서 간소화된 환경에서의 강화학습의 평가적인 측면을 연구해보자.
2.1 A k-armed Bandit Problem
다음과 같은 학습 상황을 생각해보자.
당신은 $k$개의 행동 중 하나를 선택하는 상황이 반복된다고 생각해보자.
당신은 어떤 행동을 선택하느냐에 따라 각 선택으로부터 수치적으로 표현할 수 있는 stationary 확률 분포를 따르는 보상을 받게 된다.
당신의 목표는 전체 보상의 기대값을 최대화 시키는 것이다.
예를 들어 1000가지 행동 혹은 time step에 관해서 말이다.
k-armed bandit problem의 예
- 슬롯 머신(one-armed bandit problem), 레버를 한번 당길때마다 주어지는 보상문제.
- 의사의 수술 문제, 의사가 어떤 환자를 치료하는데 k가지 치료법 중 하나를 선택.
이것이 k-armed bandit problem의 원래 형태이다.
우리가 다루는 k-armed bandit problem은
- $value$: $k$개의 행동을 선택했을 때의 평균(기대값) 보상
- $A_t$: time step $t$에 대해 선택한 행동(action)
- $R_t$: time step $t$에 대해 선택한 행동(action)에 대한 보상
- $q_{*}(a)$: 임의의 행동 $a$를 선택했을 때의 $value$
만약 당신이 각 행동에 대한 value를 안다면 k-armed bandit problem 을 푸는게 쉬워질 것이다.
왜냐면 당신은 가장 높은 value를 가지는 행동만 선택하면 되기 때문이다.
우리는 당신이 그저 추정할 수 있을 뿐이지 action value를 모른다고 가정할 것이다.
- $Q_t(a)$: time step $t$에서 행동 $a$에 대한 추정 value
- $Q_t(a)$는 $q_{*}(a)$ 에 수렴할 것이다.
당신이 action value 추정을 계속하게 되면 어떤 time step에서든 추정 값의 최대값을 구할 수 있게 되는데,
우리는 그것을 greedy action이라고 부른다.
만약 당신이 여러가지 행동 중 action value가 최대값인 행동을 선택하게 되면 우리는 그것을 exploitation 이라고 부르고,
nongreedy action 중에 하나를 선택하게 되면 우리는 그것을 exploration 라고 부른다.
왜냐하면 이것은 당신이 nongreedy action의 value의 추정치를 개선하게 만들 것이기 때문이다.
exploitation은 특정 한 단계에서 기대 보상을 극대화 시키지만,
exploration은 장기적인 관점에서 더 큰 토탈 보상을 발생시킨다.
예를 들어 greedy action value 가 확실성을 가지고 있다고 가정하면,
다른 행동들은 그만큼 좋을 순 있어도 상딩한 불확실성을 가진다.
여기서 말하는 불확실성이란, 그 행동들 중 하나는 greedy action보다 좋을 수 있지만,
문제는 그 행동이 어떤 것인지를 모른다는 것이다.
당신은 많은 time step에서 여러 개의 nongreedy action을 exploration함으로써 greedy action보다 나은 행동을 찾을 수 있다.
이는 단기적으로는 exploration할 때는 보상이 낮을 수 있지만, 장기적으로는 더 높은 보상이 생길 것이다.
왜냐하면 당신은 exploration함으로써 더 좋은 행동을 발견했기 때문에 그 행동을 많이 exploit할 것이기 때문이다.
어떤 특정 한번의 선택에서 explore와 exploit은 둘 다 선택할 수 없으며 우리는 이것을 conflict라고 부른다.
exploit과 explore의 밸런스를 조정하는 여러 방법들이 있지만, 대부분 그것들은 강력한 가정이나 사전지식을 전제로 하거나 전체 강화학습 문제에서 입증하기 어려운 것들이다. 이번 챕터에서는 exploit과 explore를 조절하는 복잡한 방법은 잊어버리고, 간단한 방법을 알아보자.
2.2 Action-value Methods
각각의 행동 선택 결정을 추정하기 위해 사용되는 action value의 추정값을 구하는 방법인 action-value method를 알아보자.
\[\begin{eqnarray} Q_t(a) & \doteq \frac{\texttt{sum of rewards when a taken prior to t}}{\texttt{number of times a taken prior to t}} \\ & = \frac{\sum_{i=1}^{t-1}R_i \cdot I_{A_{i}=a}}{\sum_{i=1}^{t-1} I_{A_{i}=a}} \end{eqnarray}\]이 때, $I_{predicate}$ 는 predicate가 true면 1, false면 0인 지시함수를 의미한다.
만약 분모가 0이면 전체 값이 0이 되는 것과 같은 디폴트 값을 쓰게 한다.
만약 분모가 무한대로 가면 큰수의 법칙에 의해 $Q_t(a)$는 $q_{*}(a)$값에 수렵한다.
우리는 이것을 관련된 보상의 샘플의 편균이므로 action-value를 추정하기 위한 방법으로 표본 평균(sample-average)방법 이라고 부른다.
action 선택을 가장 쉽게 할수 있는 방법은 가장 높은 value을 선택하는 것이다. 즉 이전 섹션에서 말한 greedy method를 쓰는 것인데, 만약 최대값이 두개 이상이라면 그 중 하나를 임의로 선택하면 된다. 우리는 greedy action을 다음과 같이 표기한다.
\[A_t \doteq argmax_{a}Q_t(a)\]이때, $argmax_{a}$는 값을 최대화 시키는 행동 a를 뜻한다. greedy aaction은 항상 즉각적인 보상을 극대화하는 행동을 exploit하는 것이므로, 이를 약간만 변형하면 아주 가끔, 그러니까 아주 작은 확률 $\epsilon$만큼 action-value 추정치와 무관한 행동을 선택하는 것이다. 우리는 이 방법을 $\epsilon-greedy$ method라고 부른다.