Chapter 1. 밴디트 문제

사람은 가르치는 선생님이 없어도 스스로 시행착오를 겪으면서 자연스럽게 배우는 것들이 있다. 이것처럼 가르치는 사람 없이도 환경과 상호작용하며 더 나은 해결책을 스스로 학습하는 것을 강화학습이라고한다.

이번 장에서 다룰 문제는 강화 학습에서 가장 기본이 되는 '밴디트 문제'이다.

머신러닝 분류와 강화 학습

머신러닝은 말 그대로 기계를 학습시키는 기법이다. 규칙을 사람이 프로그래밍 하여 알려주는 것이 아니라 컴퓨터가 데이터를 통해서 스스로 찾아 학습하는 것이다. 

머신러닝 기법들은 대표적으로 '지도 학습', '비지도 학습', '강화 학습'으로 나뉜다.

지도 학습과 비지도 학습

지도 학습은 머신러닝에서 가장 전통적인 기법이다. 지도 학습에서는 입력(문제)와 출력(정답)을 쌍으로 묶은 데이터를 사용한다. 

지도 학습의 특징은 '정답 레이블'이 존재한다는 것이다. 마치 선생님이 정답을 미리 알려주는 것이다. 이 때 선생님은 대부분 인간이다. 

반면 비지도 학습에서는 정답을 알려주는 '선생님'이 따로 없다. 오직 데이터만이 존재한다. 비지도 학습은 데이터에 숨어 있는 구조나 패턴을 찾는 용도로 주로 쓰이며 군집화, 특정 추출, 차원 축소(t-SNE) 등을 예로 들 수 있다. 

강화학습

강화 학습은 지도 학습이나 비지도 학습과는 다른 유형의 문제를 다룬다. 강화 학습에서는 다음 그림과 같이 에이전트와 환경이 서로 상호작용한다.

에이전트(Agent)는 행동 주체를 말한다. 에이전트는 환경(Environment)에 놓여쳐, 환경의 상태(State)를 관찰하고 상태에 적합한 행동(Action)을 취한다. 행동의 결과로 환경의 상태가 바뀐다. 그리고 에이전트는 환경으로부터 보상(Reward)을 받음과 동시에 변화된 새로운 상태를 관찰한다. 강화학습의 목표는 에이전트가 얻는 보상의 총합을 극대화하는 행동 패턴을 익히는 것이다. 

로봇 보행 문제를 생각해보자. 이 로봇은 현실 공간(또는 시뮬레이터)에서 직접 앞으로 나아가는 시행착오를 통해서 걷는 방법을 학습한다. 팔과 다리를 얼마나 어떻게 움직여야하는지 가르쳐주는 사람도 없다. 일단 어떻게든 움직여보면서 경험을 쌓고 그 경험을 통해서 배우는 것이다. 

강화 학습에서는 환경의 피드백으로 '보상'을 받는다. 보상은 지도 학습에서의 정답 레이블과는 성격이 다르다. 보상은 행동에 대한 피드백일 뿐, 그 보상으로부터 지금까지 취한 행동이 최적인지 여부는 판단할 수 없다. 반면, 지도 학습에서는 정답이 제공된다. 지도 학습을 강화 학습 맥락에서 생각해보면 어떤 행동을 취했을 때 '최적의 행동은 이것이다'라고 알려주는 선생님이 있다는 뜻이다.

밴디트 문제

밴디트 문제란?

밴디트는 '슬롯머신'의 또 다른 이름이다. 밴디트 문제를 정확하게는 멀티-암드 밴디트 문제(multi-armed bandit problem)이라고 한다. 

밴디트 문제에서는 슬롯머신마다 각각 좋은 그림 조합이 나올 확률이 제각각이다. 플레이어는 정해진 횟수 동안 플레이하며 어떤 머신의 승률이 가장 좋은지 실제로 플레이를 해보면서 찾아내야 한다. 정해진 횟수 안에 코인을 최대한 많이 얻는 것이 목적이다.

밴디트 문제에서 슬롯머신은 강화학습에서의 '환경'이며 플레이어는 '에이전트'이다. 플레이어가 여러 슬롯머신 중 한 대를 선택해서 플레이 하는 것이 '행동'이다. 코인의 결과가 '보상'이다. 

이처럼 에이전트와 환경이 서로 상호작용하는 것이 강화학습이 기본 메커니즘이며 밴디트 문제도 여기에 속한다. 

일반적인 강화 학습 문제에서 환경에는 상태 정보가 있다. 그러나 밴디트 문제에서는 슬롯머신들의 확률값에 변화가 없기 때문에 따로 고려할 필요가 없다. 상태가 변하는 문제는 '2장 마르코프 결정 과정'에서 다룬다.

좋은 슬롯머신이란?

예를 들어 두 슬롯머신의 확률분포가 위와 같을 때 어떤 슬롯머신이 더 좋은 슬롯머신일까? 슬롯머신의 플레이 결과는 무작위하게 변하지만 수없이 많이 플레이하면 평균적으로 어떤 하나의 값에 수렴하게 된다. 이것이 바로 기대값(expected value)이다. 슬롯머신 플레이 같은 확률적 사건은 '기대값'으로 평가할 수 있다. 무작위성에 현혹되지 않기 위해 '기대값'을 기준으로 삼아야 한다.

밴디트 문제(강화학습)에서는 보상의 기대값을 가치(Value)라는 특별한 이름으로 부른다. 행동의 결과로 얻는 보상의 기대값을 행동 가치(action value)라고 한다. 

수식으로 표현하기

보상은 'Reward'의 머리글자를 따서 R로 표기한다. Reward는 확률적으로 값이 결정되므로 확률 변수(random variable)라고 볼 수 있다. 밴디트 문제에서는 첫 번째, 두 번째 ... 식으로 행동을 연속적으로 하므로 t번째에 얻는 보상임을 명시할 때는 \(R_t\)라고 한다.

행동은 'Action'의 머리글자를 딴 A로 표기한다.

기대값은 Expection의 머리글자 딴 \(\mathbb{E}\)로 쓴다. 보상 R에 대한 기대값은 \(\mathbb{E}(R)\)이고, 행동 A를 했을 때의 보상 기대값은 \(\mathbb{E}(R|A)\)로 쓴다. 일반적으로 대문자 A는 추정치를 뜻하며 소문자 a는 실제 행동 가치를 뜻할 때가 많다.

보상에 대한 기대값을 행동 가치라고 한다. 강화 학습에서는 관례적으로 행동 가치를 Q 또는 q로 표기한다(Quality의 머리글자). 그래서 행동 가치 q(A)는 다음처럼 표기한다

$$q(A)= \mathbb{E}(R|A)$$

밴디트 알고리즘

플레이어가 슬롯머신의 '가치(보상 기대값)'을 알 수 없기 때문에 실제로 플레이하고 그 결과를 토대로 각 슬롯머신의 가치를 추정해야 한다.

가치 추정 방법

플레이어가 두 슬롯머신을 각각 세번 플레이했을 때 그 결과로부터 각 슬롯머신의 가치 추정치를 구해보자.

$$Q(a)=\frac{0+1+5}{3}=2$$

$$Q(a)=\frac{1+0+0}{3}=0.333 \cdots $$

이상의 결과에서 슬롯머신 a가 더 좋을 것이라고 추정할 수 있다. 물론 이 가치는 추정일 뿐 실제 가치와 똑같지는 않다.

총 n번 플레이하는 경우의 행동 가치 추정치 \(Q_n\)은 다음과 같다.

$$Q_n= \frac{R_1 + R_2 + \cdots + R_n}{n}$$

그리고 n-1 번째 시점의 행동 가치 추정치 \(Q_{n-1}\)의 수식은 다음과 같다.

$$\displaylines{ Q_{n-1}= \frac{R_1 + R_2 + \cdots + R_{n-1}}{n-1} \\ R_1+R_2+\cdots+R_{n-1} = (n-1)Q_{n-1}}$$

이제 \(Q_n\)을 다음과 같이 표현해보자.

위와 같이 표현하면 \(Q_n\)과 \(Q_{n-1}\)의 관계식이 도출된다. 즉, \(Q_{n-1}, R_n, n\)의 값만 알면 \(Q_n\)을 구할 수 있다. 이렇게 되면 \(Q_n\)을 구하기 위해 \(R_1, R_2, \cdots, R_{n-1}\)을 사용하지 않아도 된다(시간 효율성 증가)

이어서 위 식을 조금 더 변형해보자.

$$\begin{equation} \begin{split}   Q_n &= (1-\frac{1}{n})Q_{n-1} + \frac{1}{n}R_n \\ &=  Q_{n-1} + \frac{1}{n} (R_n - Q_{n-1}) \end{split} \end{equation}$$

위 식에서 주목할 점은 형태가 \(Q_n = Q_{n-1} + \cdots \)라는 것이다. 다시 말해 \(Q_n\)은 \(Q_{n-1}\)에 어떤 값을 더해 구할 수 있다. 여기서 \(Q_{n-1}, Q_{n}, R_n\)의 위치 관계는 다음 그림과 같다.

그림에서 보듯  \(Q_{n-1}\)이  \(Q_{n}\)으로 갱신될 때 \(R_n - Q_{n-1}\)에 \(\frac{1}{n}\)을 곱한 만큼 이동한다. 이때 \(R_n\) 방향으로 얼마나 진행되느냐는 \(\frac{1}{n}\)이 결정하기 때문에 학습률(learning rate) 역할을 한다고 볼 수 있다.

코드로 구현하면 다음과 같이 구현할 수 있다.

플레이어의 정책

이제 플레이어가 어떤 전략을 취해야 하는지 생각해보자. 각각을 플레이해보고 가치 추정치(실제 획득한 보상의 평균)이 가장 큰 슬롯머신을 선택할 수 있다. 이것이 탐욕 정책(greedy policy)이다. 

하지만 이런 탐욕 정책은 확실하지 않은 가치 추정치에 전적으로 신뢰하기 때문에 한게가 있다. 따라서 플레이어는 다음의 두 가지 행동이 필요하다

• 활용(exploitation): 지금까지 실제로 플레이한 결과를 바탕으로 가장 좋다고 생각하는 슬롯머신을 플레이. 탐욕 정책
• 탐색exploration): 다양한 슬롯머신을 시도

활용과 탐색은 트레이드 오프 관계에 있다. 강화 학습 알고리즘은 결국 '활용과 탐색의 균형'을 어떻게 잡느냐의 문제로 귀결된다. 가장 기본적이고 응용하기 좋은 방식은 ε-greedy 정책이다.

ε-greedy 정책은 ε=0.1의 확률로 '탐색'을 하고 나머지는 활용을 하는 방식이다. 탐색할 차례에서는 무작위 행동을 통해 다양한 경험을 쌓는다. 이렇게 함으로써 가능한 모든 행동 각각의 가치 추정치의 신뢰도가 조금씩 높아진다. 그리고 나머지 1-ε의 확률로 탐욕 행동, 즉 활용을 수행한다.

ε 값에 따른 승률 변화 비

비정상 문제

지금까지 다룬 밴디트 문제는 분류상 정상 문제(stationary problem)에 속한다. 정상 문제란 보상의 확률 분포가 변하지 않는 문제이다. 즉 슬롯머신의 속성은 한 번 설정되면 변하지 않는다.

정상성(Stationary)?
시간에 상관없이 일정한 성질을 띠고 있는 것
‘약 정상성을 띠는 시계열 데이터는 어느 시점(t)에 관측해도 확률 과정의 성질(E(Xt), Var(Xt))이 변하지 않는다’

반대로 확률 분포가 변하도록 설계를 한 문제를 '비정상 문제(non-stationary problem)'이라고 한다.

비정상 문제를 풀기 위해서

비정상 문제를 풀기 위해서 위에서 살펴본 다음 식을 살펴보자.

$$\begin{equation} \begin{split}   Q_n &= \frac{R_1 + R_2 + \cdots + R_n}{n}  \\ &= \frac{1}{n}R_1 + \frac{1}{n}R_2 + \cdots +  \frac{1}{n}R_n  \\ &=  Q_{n-1} + \frac{1}{n} (R_n - Q_{n-1}) \end{split} \end{equation}$$

위 식에서 주목할 점은 모든 보상 앞에 \(\frac{1}{n}\)이 붙어있다는 점이다. 이 것을 각 보상에 대한 '가중치'로 생각할 수 있다.

이제 이 가중치 \(\frac{1}{n}\)을 \(\alpha\)라는 고정값으로 바꿔보자(0 < \(\alpha \) < 1).

$$Q_n  = Q_{n-1} + \alpha(R_n - Q_{n-1})$$

그리고 이 식을 다시 전해개보자.

$$\begin{equation} \begin{split}  Q_n &= Q_{n-1} + \alpha(R_n - Q_{n-1})  \\ &= \alpha R_n + Q_{n-1} - \alpha Q_{n-1} \\ &= \alpha R_n + (1-\alpha) Q_{n-1} \end{split} \end{equation}$$

이렇게 쓰면 \(Q_n, Q_{n-1}\)의 관계가 명확해진다. 이제 n 대신 n-1을 대입하면,

$$Q_{n-1}  = \alpha R_{n-1}  + (1-\alpha) Q_{n-2}$$

그럼 다음과 같이 정리가 가능하다. 

 식 1.9를 보면 \(R_n\)의 가중치는 \(\alpha\)이고 \(R_{n-1}\)의 가중치는 \(\alpha(1-\alpha\)이다. 지금까지의 과정을 \(Q_{n-2}\)에도 적용해보자.

$$Q_n = \alpha R_{n}  + (1-\alpha) R_{n-1}  + (1-\alpha)^2 R_{n-2}   + (1-\alpha)^3 Q_{n-3}$$

이상의 전개를 n번 반복하면 다음 식이 만들어진다.

$$Q_n = \alpha R_{n}  + \alpha (1-\alpha) R_{n-1}  + \cdots + \alpha (1-\alpha)^{n-1}R_{1}   + (1-\alpha)^n Q_{0}$$

위 식을 보면 \(R\)의 가중치가 기하급수적으로 감소하고 있음을 알 수 있다.

$$\alpha, \space \alpha (1-\alpha), \space  \alpha (1-\alpha)^2, \space   \alpha (1-\alpha)^3  \space... $$

이처럼 지수적으로 감소하기 때문에 위 식의 계산을 지수 이동 평균 도는 지수 가중 이동 평균이라고 한다.

위 식에서 주의할 점은 \(Q_n\)을 구하는 데 \(Q_0\)의 값이 사용되었다는 것. \(Q_0\)의 값은 행동 가치의 초기값으로 우리가 설정하는 값이다. 따라서 우리가 설정하는값에 따라 학습 결과에 편향(bias)가 생긴다. 반면 표본 평균의 경우 이러한 평향이 생기지 않는다. 표본 평균은 첫 번째 보상을 받으면 사용자가 부여한 초기값은 사라진다고 할 수 있다.

정리

• 강화학습은 머신러닝의 한 분야이지만 지도 학습, 비지도 학습과는 분명한 차이가 있다.
• 강화 학습은 환경과 에이전트의 상호작용으로 이루어지며, 자신의 행동에 대해 보상을 얻고 보상의 총합을 극대화하는 행동 패턴을 익히는 것을 목표로 삼는다.
• 밴디트 문제 그리고 강화 학습에서는 활용과 탐색의 균형을 맞추는 일이 중요하다.
• ε-greedy 정책은 지금까지 얻은 경험을 활용함과 동시에 가끔은 탐욕스럽지 않은 행동을 탐색한다.
• 참고로 밴디트 알고리즘으로는 ε-greedy 외에 UCB(Upperconfidence Bound), 그래디언트 밴디트 알고리즘 등이 있다.
• 정상 문제에는 표본 평균을, 비정상 문제에는 지수 이동 평균을 사용한다.