Ch2. Multi-armed Bandit (1) A k-armed Bandit Problem

이 글은 Richard S. Sutton과 Andrew G. Barto의 Reinforcement Learning: An Introduction second edition을 기반으로 하고 있습니다. 개인적인 주관과 지식으로 인해 틀린 내용이 있을 수 있으므로 피드백이나 질문은 언제나 환영입니다.

P.S. 1장은 강화학습에 대한 소개이기 때문에 생략했다.

Part I: Tabular Solution Methods

Part I에서 다루는 강화학습은 상태와 행동의 수가 작아서 가치 함수를 배열(array)이나 테이블(table) 형태로 나타내어 문제를 푼다. 그렇기에 정확하게 최적의 가치함수와 정책을 구할 수 있다. 하지만 상태와 행동의 수가 큰 문제의 경우에는 사용할 수 없는 방법이다. 따라서 Part 2에서는 이를 근사(approximate)해서 정확하지 않지만 최적의 가치와 정책에 가깝게 찾아낸다.

• Chapter 2 : 상태가 오로지 하나인 bandit 문제를 다룬다.
• Chapter 3 : 일반적으로 문제를 표현하는 식 MDP(Markov Decision Processes)을 설명한다. (Bellman 방정식과 가치함수도 포함)
• Chapter 4, 5, 6 : 위 문제를 해결하기 위한 다른 세 가지 방법이 나오는데, 효율성이나 수렴 속도가 다르다.
  • Dynamic Programming(4). 수학적으로 잘 발달되어 있지만 완전히 정확하게 환경의 모델을 계산해야 한다.
  • Monte Carlo methods(5). 모델이 필요없고 개념적으로 쉽지만, step-by-step incremental computation에는 적합하지 않다.
  • Temporal-difference learning(6). 모델이 필요없고 incremental computation을 하지만, 분석하기에 복잡하다.
• 나머지 두 챕터에서는 위 방법들의 특징들을 가져와 조합하는 것을 보인다.
  • Monte Carlo와 Temporal Difference를 조합한 multi-step bootstrapping
  • Temporal Difference와 model learning and planning methods의 조합

Chapter 2 Multi-armed Bandit

강화학습의 큰 특징 중 하나는 옳은 행동을 가르쳐 주는(instruct)게 아니라 했던 행동을 평가(evaluate) 한다는 것이다. 자전거를 탈 때처럼, 핸들을 어떤 방향으로 틀어라, 패달을 밟아라 등 그 때 그 때 알려주는 것이 아니라 이렇게도 해보고 저렇게도 해보고(exploration) 시행착오(trial-and-error)를 겪으면서 어떻게 하면 자전거를 앞으로 나아가게 하는지 (good behaivor)를 깨닫는다. 여기서 말하는 평가는 행동이 최악인지 최고인지 딱 알려주는 것이 아니라, 좋다 나쁘다 정도만을 얘기해주는 것이다.

• 평가 피드백(evaluative feedback)은 행동한 것을 보고 잘했는지 안했는지 알려주는 것. (강화학습)
• 교육 피드백(instructive feedback)은 행동한 것과는 상관없이 해야될 행동(정답)을 알려주는 것. (지도학습)

이번 챕터에서는 이런 평가(evaluative) 측면에서 공부해보기 위해, 하나의 상황(situation)만 있는 단순하게 설정(nonassociative)을 가지고 살펴볼 것이다. 그래서 교육 피드백(instructive feedback)과 어떻게 다른지 보게 되고, 이와 조합할 수 있다는 것을 알 수 있을 것이다.

nonassociative, evaluative feedback 문제는 바로 k-armed bandit problem으로 여기서 다루는 기본적인 학습 방법이 나중에 다룰 강화학습 문제로 확장해 적용할 수 있다.

nonassociative라는 말은 연관이 없다는 말인데, 행동과 관련이 없다는 얘기인 것 같다. 즉, 행동이 상황에 영향을 주지 않는다라는 말로, 행동을 해도 그 안에 상황은 다르게 변하지 않는다는 것이다.

2.1 A k-Armed Bandit Problem

카지노에 가지 않더라도 영화나 드라마를 보면 한 번쯤 보는 어떤 기계가 있다. 바로 슬롯 머신(Bandit Machine)이다. 왼쪽에 손잡이룰 내리면 찡찡찡 소리 내면서 짝이 맞으면 돈을 주는 그런 기계다.(사실 나도 어찌하는지 잘 모른다. 일단 돈을 준다고 하자)

이런 기계가 여러 개(k개) 있어서 하나 선택해서 슬롯을 돌릴 수 있으며 각각 고정된 확률(stationary probability)로 돈(reward)이 나온다. 목표는 주어진 시간 안에 돈을 최대한 많이 따는 것이다.

강화학습에서는 목적을 주어진 시간안에 기대되는 보상의 합을 최대화한다고 표현한다. (To maximize the expected total reward over some time steps)

위와 비슷한 문제는 bandit problem이라고 보통 부른다. 예를 들어 환자가 한명 있고 치료 방법이 k개 있어서 하나를 선택해야 하는 문제도 동일하게 볼 수 있다.

각 행동은 받을 것이라 기대되는 보상(expected reward)이나 평균 보상(mean reward)이 있을 것이다. 이를 행동의 가치(value)라 부르겠다. time step $t$에서의 행동을 $A_t$, 그 행동으로 얻는 보상을 $R_t$라 정의하고, $q_\ast(a)$는 행동 $a$ 했을 때 받을 것이라 기대되는 보상(expected reward)이라 정의하여 다음과 같이 표현한다.

expected value의 표현으로 사용하는 $\mathbb{E}$는 통계학에서 나오는 개념이다. 내 설명보다는 아주 잘 설명된 데이터 사이언스 스쿨 설명을 참조하자.

당연히 기대되는 보상이 큰 행동을 하면 보상을 많이 얻을 수 있다. 즉, $q_\ast(a)$값이 큰 행동 $a$를 항상 선택하면 된다. 하지만, 아직까진 가치값을 몰라서 이를 추정(estimate)해보기로 하고 $Q_t(a)$이라 정의하여 $q_\ast(a)$에 가깝게 알아내야한다.

일단 추정한 가치(estimated value)가 있다고 하고 정확하지는 않겠지만 이 중에서도 최고인 값을 가진 행동이 있을 것이다. 이를 greedy action이라 한다.

이렇게 추정한 가치를 통해 최고값을 가진 하나의 행동을 고르는 것은 자신이 알고있는 행동의 가치를 활용(exploit)한다고 볼 수 있다. 그런데 $a$ 행동으로 얻을 것이라 기대되는 보상 $q_\ast(a)$을 몰라서 추정한 가치 $Q_t(a)$를 사용하기 때문에 무조건 greedy action을 고른다고 해서 좋은 게 아닐 수 있어서 greedy action이 아닌 행동(nongreedy action)을 선택해봐야 한다. 기존에 몰랐던 또다른 행동에 대한 보상을 알 수 있을 것이고 이를 다시 활용(exploit)하면 앞으로 더 좋은 행동을 할 수 있다. 이렇게 nongreedy action을 선택하는 것은 마치 탐험(explore)하는 것과 같다.

그렇다면 딜레마에 빠진다. 언제 exploit하고 언제 explore해야하는가? 이러한 balancing exploitation and exploration은 여전히 해결해야할 강화학습 문제 중 하나이며, 다양한 방법들로 이를 해결하려고 하고 있다. 이 책에서는 복잡한 방법까지는 고려하지 않고 몇 가지 방법만 다룰 것이다.