Chapter 2: Multi-armed Bandits

머신러닝에서 말하는 피드백에는 크게 두 가지가 있습니다. Instructive feedback은 무엇이 올바른 행동인지 알려주며 지도 학습(supervised learning)의 토대가 되는 반면, evaluative feedback은 어떤 행동이 얼마나 좋은지를 수치적으로 말해주며 강화학습에서 중요한 역할을 합니다. 본 챕터에서는 강화학습의 evaluative feedback을 매우 단순화된 세팅에서 살펴보도록 합니다.

2.1 A k-armed Bandit Problem

k-armed Bandit이란 k개의 레버가 달린 슬롯머신입니다. 레버들을 당기면 각기 다른 확률분포에 따라 보상이 나오며, 각 확률분포가 어떻게 되는지 처음에는 알지 못합니다. 각 레버들이 주는 보상값들을 기록해 나가다보면 어떤 레버가 높은 보상을 주는지 추정할 수 있습니다. 매 턴(time step)마다 이제까지 계산한 것 중 가장 높은 보상 추정치를 가진 레버를 당기는 것을 greedy action이라고 하며, 현재 지식을 활용(exploit)한다고 합니다. 반면 가장 높은 추정치가 아닌 레버를 당겨보는 것은 탐색(explore)이라고 합니다. 단기적으로는 greedy action이 보상이 높지만, 장기적으로는 explore를 어느 정도 하는 것이 실질적으로 더 높은 보상의 확률 분포를 가진 레버를 찾아낼 확률이 높아집니다.

2.2 Action-value Methods

어떤 턴(time step) t에서 선택한 행동(action)을 \(A_t\)로 표기하고 그에 따른 보상(reward)을 \(R_t\)로 표기합니다. 가치를 표기하는 q*(a)는 행동 a를 선택했을 때의 기대 보상치를 의미하고, \(Q_t(a)\)는 time step t에서 추정하는 q값을 의미합니다. 이 책에서 보통 *가 붙으면 실제의 참값(true value) 혹은 최적값(optimal value)를 의미합니다. 즉, 전자는 해당 행동의 실제 보상이 무엇인지를 표기하고, 후자는 우리의 에이전트가 생각하는 보상 추정치를 의미합니다. 우리의 목표는 \(Q_t(a)\)가 최대한 q*(a)에 가깝도록 학습하는 것입니다. 가장 기초적인 학습 방법은 실제 받은 보상들의 평균을 취하는 sample-average method이지만, 이것이 가장 좋은 방법인 것은 아닙니다.

여러 행동을 통해 계산한 추정치 중 가장 높은 것을 고르는 것이 greedy method이라고 한다면, \(\epsilon\)-greedy method는 1-\(\epsilon\)의 확률로는 greedy action을 취하고, \(\epsilon\)의 확률로는 모든 action을 동일 확률로 선택하는 것입니다. 예를 들어 \(\epsilon\)이 0.2일 때 다섯 개의 레버가 있고(k=5), 2번째 레버의 보상을 가장 높다고 추정하고 있다고 합시다. 그러면 \(\epsilon\)-greedy 방법을 따른다면, 우리의 에이전트는 80% 확률로는 2번째 레버를 당기고, 20% 확률로는 5개의 레버 중 하나를 무작위로 당깁니다. 여기서 5개의 레버에 2번째도 포함되므로, 1, 2, 3, 4, 5번 레버를 당길 확률은 각각 4%, 84%, 4%, 4%, 4%가 됩니다. 이 방법을 사용하면 항상 최고 추정치를 가진 레버만 당기는 것(exploitation)이 아니라, 탐색(exploration)도 어느 정도 하게 되서, 현재 추정치는 낮지만 실제로는 높은 확률 분포를 가진 레버를 찾을 수 있게 됩니다. 이것이 exploration과 exploitation의 밸런스를 맞추는 가장 기초적인 방법 중 하나입니다.

2.3 The 10-armed Testbed

아래는 10개의 레버가 있는 테스트 환경에서 여러 \(\epsilon\)에 따른 평균 보상값입니다. 아예 greedy action을 취하는 \(\epsilon=0\)일 경우에 장기적으로 보상이 나아지지 않지만, exploration을 하는 0.1과 0.01의 경우는 점진적으로 더 나은 레버를 탐색해 나가며 보상이 높아집니다.

출처: Sutton and Barto Textbook p.29

그러나 항상 \(\epsilon\)-greedy 방법이 좋은 것은 아닙니다. 예를 들어, 실제 보상값의 표준편차가 0이거나 거의 없으면, 괜히 \(\epsilon\)의 확률로 다른 레버를 탐색할 것 없이 계속 greedy action을 취하는 것이 보상값이 더 높을 것입니다. 그러나 그렇지 않을 경우, 혹은 레버의 보상값이 고정된 확률 분포를 따르는 것이 아니라 시간에 따라 달라질 경우에는 \(\epsilon\)-greedy 방법이 더 좋은 결과를 줍니다.

2.4 점증 방식(Incremental Implementation)

보상 추정치를 계산하는 방법 중 샘플 평균 방식(sample-average method)에 대해 알아봅시다. i번째 action에 따른 보상을 /(R_i/)라 하고 n-1번 선택된 후의 그 action의 추정치를 \(Q_n\)라고 한다면, \(Q_n = \frac{R_1+R_2+...+R_{n-1}}{n-1}\)로 적을 수 있습니다. 이걸 실제로 실행할 때 매번 위의 식을 계산하는 것은 비효율적이기 때문에, \(Q_{n+1} = Q_n + \frac{1}{n}[R_n - Q_n]\) 으로 계산하면 메모리와 계산을 줄일 수 있습니다.

더 일반적으로 적으면 \(NewEstimate \leftarrow OldEstimate + StepSize[Target - OldEstimate]\)이 됩니다. 샘플 평균 방식의 예에서는 StepSize parameter를 \(\frac{1}{n}\)으로 정의했지만, 일반화하면 \(\alpha\) 혹은 \(\alpha_t(a)\)로 표기합니다. 유사코드(pseudocode, 실제 코딩 언어의 문법을 따른 것이 아니라 가독성과 의사 전달을 목적으로 표현한 컴퓨터 코드)로 표현하면 아래와 같습니다.

출처: Sutton and Barto Textbook p.32

• 프로그램이 시작할 때 가장 먼저 모든 k개의 레버 action에 대하여 그 보상추정치인 Q(a)와 당겨본 횟수 N(a)를 0으로 초기화(initialize)합니다.
• 그 다음 무한 루프에 들어갑니다. (실제 코드에서는 더 이상 업데이트가 어떤 값 이상 되지 않으면 끝내는 것으로 코딩합니다)
• 루프의 각 step을 시작할 때 먼저 어떤 action을 취할지 A를 정해야하는데, \(1-\epsilon\)의 확률로는 현재 추정치 Q(a) 중 가장 높은 추정치를 가진 action을 취하고, \(\epsilon\)의 확률로는 모든 k개의 action 중 하나를 무작위로 취합니다.
• 그렇게 정한 A를 따라 레버를 당겨 보상 R을 받고, 해당 action인 A의 당긴 횟수 N(A)에 1을 더해줍니다.
  마지막으로 보상 추정치를 위에서 다룬 incremental 방식으로 업데이트 합니다.

2.5 Tracking a Nonstationary Problem

각 레버의 보상 확률 분포가 계속 변하지 않으면 stationary라고 하고, 시간에 따라 계속 변하면 nonstationary라고 합니다. 각 레버의 보상치가 변하지 않을 때(stationary)는 이제까지 경험한 보상을 단순히 평균하는 것이 유효하지만, 그렇지 않을 경우(nonstationary)는 최근에 받은 보상값에 더 무게를 둘 필요가 있습니다.

\(Q_{n+1} = Q_n + \alpha [R_n - Q_n]\)에서 \(\alpha\)값을 \(\frac{1}{n}\)이 아닌 상수로 두면,

\(Q_{n+1} = \alpha R_n + (1 - \alpha)\alpha R_{n-1} + (1-\alpha)^2 \alpha R_{n-2} + ... + (1-\alpha)^{n-1} \alpha R_1 + (1-\alpha)^n Q_1\) 이 되어 기하급수적으로 최근 값에 가중치를 부여하게 됩니다. 이를 exponential recency-weighted average 라고 합니다.

만일 상수가 아니라 \(\alpha_n(a) = \frac{1}{n}\)처럼 step 별로 다른 값을 두려면, 1) \(\sum_{n=1}^{\infty}\alpha_n(a) = \infty\)와 2) \(\sum_{n=1}^{\infty}\alpha_n^2(a) < \infty\)의 두 가지 조건을 충족해야 추정치가 n이 커짐에 따라 수렴(converge)합니다. 첫번째 조건은, 초기값이나 무작위성에서 오는 노이즈에 휘둘리지 않도록 step size가 충분히 크도록 보장해주고, 두번째 조건은 n이 커지면 step들이 충분히 작아져서 convergence를 보장할 수 있도록 해줍니다. 앞서 다룬 sample-average 방법은 이 두 가지를 충족하지만, 바로 위의 exponential recency-weighted average는 두번째 조건을 충족하지 않습니다. 그렇기에 n이 아무리 커져도 수렴(converge)하지 않고 최근값에 따라 계속 변하게 되는데, 만일 k개의 레버의 보상값이 시간에 따라 달라지는 non-stationary environment일 경우 이는 우리가 원하는 바입니다.

2.6. Optimistic Initial Values

이제까지 다룬 방법들은 Action-value 추정치의 초기값인 \(Q_1(a)\)에 영향 받습니다. Sample-average 방법의 경우 모든 action이 한번씩 행해지고 나면 이 편향(bias)은 사라지지만, 상수 \(\alpha\)를 사용할 경우 시간이 지남에 따라 줄어들긴해도 지속적인 영향을 받습니다.

이 bias를 이용하는 간단한 방법 중 하나가 초기값을 낙관적(optimistic)으로 세팅하는 것입니다. 실제 매우 높게 초기값을 선택하면, 당겨본 레버들의 보상추정치가 당겨보지 않은 레버들보다 훨씬 낮게 되면서, 모든 레버들을 다 explore해보게 됩니다. 이 방식으로 greedy 방법을 사용하였을 때, 아래와 같이 \(\epsilon\)-greedy 방법보다 초기에는 보상이 낮지만 그 이후에는 더 많은 보상을 얻을 수 있음을 알 수 있습니다.

Source: Sutton and Barto Textbook, p.34

그러나 실제 보상 분포가 변화하는 nonstationary environment의 경우, 초기값은 초반에만 영향을 주고 분포가 달라지면 그 영향이 사라지기 때문에 이 방식이 의미가 없습니다.

2.7 Upper-Confidence-Bound Action Selection

더 나은 보상을 주는 레버를 찾기 위한 탐색(exploration)은 중요합니다. \(\epsilon\)-greedy 방법은 탐색을 하도록 해 주지만, 모든 행동(action) 중에 무작위로 선택을 할 뿐입니다. Upper confidence bound action selection 방법은, 단순 무작위가 아닌 현재 추정값들의 신뢰구간을 이용합니다.

\(A_t = argmax_a [Q_t(a) + c\sqrt{\frac{\ln t}{N_t(a)}}]\)

여기서 \(Q_t(a)\)는 현재 추정값이고, 양수인 c는 얼마나 탐색(exploration)을 권장할지 특정하는 파라미터입니다. c값이 클수록 신뢰구간이 넓어지므로 탐색을 권장합니다. 그 다음 제곱근 안의 숫자는 해당 레버를 당겨본 횟수 \(N_t(a)\)가 많아질수록 줄어드는 값입니다. ln t는 시간과 함께 불확실성이 증가하는 것을 의미하고 로그함수를 쓴 이유는 가면 갈수록 불확실성이 증가하는 속도가 느려지게 하기 위함입니다. 분모의 \(N_t(a)\)는 해당 레버를 많이 당긴 횟수이므로, 해당 레버를 많이 당겨 보았을수록 불확실성이 줄어듬을 의미합니다. 요컨대 confidence interval은 \(Q_t(a)\)를 기준으로 lower bound는 \(- c\sqrt{\frac{\ln t}{N_t(a)}}\), upper bound는 \(+ c\sqrt{\frac{\ln t}{N_t(a)}}\)를 추가한 구간입니다. 이 UCB 방법은 upper bound가 가장 높은 액션을 선택합니다. 다시 말해 신뢰오차 하에서 가장 높을 가능성이 있는 선택을 하는 것입니다. 예를 들어, 보상 추정치가 레버 A가 레버 B보다 높고, 레버 A는 많이 당겨봤지만 B는 많이 당겨보지 않았다고 가정해 봅시다. 이 경우, greedy 방법은 레버 A를 당기겠지만, UCB 방법에서는 많이 당겨보지 않은 레버 B의 신뢰구간이 훨씬 넓을 것이므로 레버 B를 당기게 됩니다.

출처: Sutton and Barto Textbook, p.36

10-armed testbed 문제에서 UCB 방법은 위에서 보는 것과 같이 \(\epsilon\)-greedy 방법보다 높은 보상을 받으나, 향후 더 일반화된 강화학습 세팅에서 적용하기에는 1) nonstationary environment에서 더 복잡한 수정을 더해야하고, 2) 거대한 state space에서 사용되는, 차후에 설명할 함수 근사(function approximation) 방식을 적용하기에 어려움이 있습니다.

2.8 Gradient Bandit Algorithms

이제까지 action value를 추정하는 방법에 대해 알아보았습니다. 또 한 가지 방법을 더 소개하자면, 각 action에 대한 수치적인 선호도(numerical preference) \(H_t(a)\)를 학습하는 방법이 있습니다. \(H_t(a)\)의 절대적인 수치 자체는 큰 의미를 가지지 않고, action들 간의 H값 차이만이 중요합니다. 각 action에 대한 선택 확률은 \(H_t(a)\)를 사용한 softmax distribution을 따릅니다.

\(Pr\{A_t=a\} = \frac{e^{H_t(a)}}{\sum_{b=1}^k e^{H_t(b)}} = \pi_t(a)\)

어떤 action을 취할 확률 \(\pi_t(a)\)는, 먼저 그 action의 H값으로 e의 H승을 취한 후, 모든 action들의 e의 H승 값들을 다 더한 분모값으로 나누어 줍니다. 그렇게 나누면 각 action들의 \(\pi_t(a)\)값을 모두 더했을 때 1이 되므로 확률값의 조건을 만족합니다.

알고리즘을 시작할 때 먼저 모든 action의 H 초기값을 0으로 둡니다. 그러면 모든 action들이 선택될 확률이 다 같게 됩니다. 그 다음 stochastic gradient descent와 비슷한 방식을 이용하여 매 step마다 아래와 같이 H값을 업데이트 합니다. (Gradient descent에 대해서는 스탠포드 Andrew Ng 교수님이 Coursera Deep Learning Lecture 1, Week 2에서 상세히 설명해 놓으신 것을 보시길 권장합니다)

\(H_{t+1}(A_t) = H_t(A_t) + \alpha (R_t - \bar R_t)(1 - \pi_t(A_t))\),       and
\(H_{t+1}(a) = H_t(a) - \alpha (R_t - \bar R_t)\pi_t(a)\),                              for all \(a \neq A_t\)

첫번째 식은 이번 step에서 선택된 action의 H값을 업데이트하고, 두번째 식은 나머지 action들의 H값을 업데이트 합니다. \(\alpha\)값은 learning rate이고, \(R_t\)는 이번 step에서 받은 보상, 그리고 \(\bar R_t\)는 이제까지 받은 보상의 평균입니다. 즉, 이번 step에서 action을 취한 후 받은 보상이 이제까지 받은 평균 보상보다 높으면, 해당 action의 H값을 높여줍니다. Learning rate이 높을 수록, 이번 보상이 평균값보다 많이 높을 수록, 그리고 해당 action의 선택될 확률이 현재 낮으면 낮을수록 H값을 더 많이 높여줍니다. 두번째 식에서는 그 반대입니다. 해당 action의 보상이 평균보상보다 높을수록 다른 action들의 H값은 낮춰줍니다 더 자세한 공식 유도는 페이지 38-40에 나와 있습니다.

2.9 Associative Search (Contextual Bandits)

이제까지의 k-armed bandit의 경우, 여러 가지 상태(state)라는 개념이 부재한 nonassociative task였습니다. "여러 가지 상태"이 무엇인가하면, 예를 들어 슬롯머신의 불이 빨강, 초록, 파랑 셋 중 하나로 표시되면서 각기 다른 보상을 줄 때, 그 세 가지 다른 색의 상태를 말합니다. 그러면 우리는 불이 파랑일 때는 두번째 레버가 보상이 가장 높고, 초록일 때는 네번째가 가장 높다는 등의 판단을 해야 합니다. 이렇게 상태(state)가 여러 가지가 있을 때, 우리는 보상값을 단순하게 추정하기보다는 정책(policy), 즉 상태(state)을 행동(action)에 매핑하는 함수를 학습해야 합니다.

이러한 문제를 associative search task, 혹은 contextual bandit 문제라고 합니다. 이 문제는 k-armed bandit과 완전한 강화학습 문제의 중간 정도에 있습니다. 완전한 강화학습 문제는 여기서 더 나아가, 현재 취하는 행동이 그 다음 step에서의 상태(state)에 영향을 미칠 경우까지 가정합니다.

2.10 요약

이 챕터에서 exploration과 exploitation을 밸런싱하는 여러 방법에 대해 알아보았습니다.\(\epsilon\)-greedy는 작은 확률로 action을 무작위 선택하고, UCB 방법은 많이 취해보지 않은 action을 더 선호함으로써 exploration을 유도합니다. Gradient bandit은 softmax distribution을 통해 각 action의 선호도를 조정합니다. 또한 초기값을 낙관적으로 설정함으로써 exploration을 유도하는 방식도 있습니다. 이러한 알고리즘 중에 가장 좋은 방법은 무엇일까요?

10-armed testbed에 대해 이 알고리즘들을 돌려볼 경우, 문제는 알고리즘마다 설정해야할 parameter들이 있다는 점입니다. 이 경우, Y축은 처음 1000 step들을 돌렸을 때 받는 평균 보상값, X축은 각 parameter들의 다른 값들로 두고 그래프를 그려볼 수 있습니다. 이를 parameter study라고 합니다.

출처: Sutton and Barto Textbook, p.42

이 특정한 문제에서는 UCB가 가장 보상이 높지만, 이 방법들 모두 exploration과 exploitation을 엄밀하게 밸런싱 잘 했다고 보긴 힘듭니다. 많이 연구된 방법 중에 하나는 Gittins index라는 action value를 계산하는 것인데, 이는 Bayesian 방법 중 하나이고, conjugate prior distribution(베이지안 업데이트를 할 때 prior와 posterior가 같은 형식의 distribution을 가질 때를 말합니다)들에 한해서는 계산과 업데이트가 매우 쉽습니다. Posterior sampling 혹은 Thompson sampling이라고 하는 이 방법은 많은 문제에서 가장 좋은 보상을 받습니다.