CHAPTER 02 다중선택

강화학습의 특징

올바른 행동을 알려주는 지침(instruct)가 아닌 행동의 좋고 나쁨을 평가(evaluate)하는 훈련 정보를 사용

=>능동적인 탐험, 즉 좋은 행동을 찾기 위한 직접적인 탐색이 필요

전적으로 평가적인 피드백은 취해진 행동이 얼마나 좋은 지를 나타낼 뿐, 그것이 발생할 수 있는 최상/최악의 행동인지를 알려주진 않음

지침적인 피드백은 실제로 취해진 행동과는 상관없이 취해야 할 올바른 행동을 알려줌

=>평가적인 피드백은 취해진 행동에 전적으로 의존하는 반면, 지침적인 피드백은 취해진 행동과는 무관하게 이뤄짐

 

하나의 상황에 대해서만 행동을 학습

비연합(nonassociative)구조는 평가적인 피드백을 포함하는 과거 대부분의 연구들이 가정한 구조

해당 구조에서는 강화학습 문제를 전체적으로 다룰 때 발생하는 문제의 복잡성을 상당 부분 피할 수 있음

평가적 피드백이 지침적 피드백과 얼마나 다른지, 그럼에도 그 둘을 어떻게 결합할 수 있는지를 가장 분명하게 확인가능

2.1 다중 선택 문제

k개의 서로 다른 옵션이나 행동 중 하나를 반복적으로 선택해야함

매 선택 후에는 숫자로 된 보상이 주어짐

이 때, 보상을 나타내는 값은 선택된 행동에 따라 결정되는 정상 확률분포(시간에 따라 변하지 않는 확률분포)로부터 얻어짐

선택의 목적은 일정기간동안 주어지는 보상의 총량에 대한 기댓값을 최대화하는 것

=>다중 선택 문제(k-armed bandit problem)의 원형

다중 선택이란 이름은 k개의 레버(선택)을 갖는 다는 점만 제외하면 슬롯 머신, '단일 선택(one-aimed bandit)'과 유사하기 때문에 붙여짐

매번 행동을 선택하는 것은 여러 개의 슬롯 머신 중 하나의 레버를 당기는 것과 같고, 선택한 행동이 가져오는 보상은 잭팟을 터뜨렸을 때 받는 상금

반복적으로 행동을 선택하면서 최고의 보상을 주는 레버에만 집중하게 됨으로써 보상을 최대로 만드는 것이 선택의 목적

 

다중 선택 문제에서 k개의 행동 각각에는 그 행동이 선택되었을 때 기대할 수 있는 평균 보상값이 할당됨

평균 보상값을 그 행동의 가치(value)라고 부름

시간 단계 t에서 선택되는 행동은 At라고 표현하고 그에 따른 보상은 Rt로 표현

이제 임의의 행동 a의 가치 q*(a)는 행동 a가 선택되었을 때 얻는 보상의 기댓값(아래와 같이 표현)

만약 모든 행동의 가치를 이미 알고 있다면 다중 선택 문제를 푸는 것은 식은 죽 먹기

언제나 가장 큰 가치를 주는 행동을 선택하면 그만

하지만 행동의 가치를 추정할 수 있더라도 확실히 알지 못한다는 것이 기본 전제

시간 단계 t에서 추정한 행동 a의 가치는 Qt(a)로 표현하는데, 추정값 Qt(a)가 기댓값 q*(a)와 가까워질수록 정확한 추정

 

행동의 가치를 추정할 수 있다면 각 시간 단계마다 추정 가치가 최대인 행동을 하나 이상 결정 가능

최대의 가치를 갖는 이러한 행동을 탐욕적(greedy)행동이라고 부를 수 있음

탐욤적 행동을 선택하는 것은 행동의 가치에 대해 현재까지 갖고있는지식을 활용(exploiting)하는 것

탐욤적 행동이 아닌 다른 행동을 선택하는 것은 비탐욕적 행동의 추정가치를 상승시킬 수 있으므로 이것은 탐험(exploring)

단 한번의 행동에 대해 최대의 보상을 원한다면 활용이 바람직하지만, 장기적으로 보상의 총합을 키우기 위해서는 탐험이 더 좋은 선택이 될 수도 있음

하나의 행동을 선택할 때 활용과 탐험을 동시에 할 수 없기 때문에 종종 활용과 탐험의 갈등(conflict)으로 인식

 

활용/탐험을 둘 중 뭘 할지 좋을지는 정밀한 가치 추정값과 불확실성, 앞으로 남아 있는 단게의 개수에 따라 복잡한 방법으로 결정됨

다중 선택 및 그와 관련된 문제를 풀기 위한 특별한 수학적 과정에 있어, 활용과 탐험 사이의 균형을 잡을 수 있게 해주는 정교한 방법이 많이 존재

대부분은 정적인 사전 지식에 대한 가정을 기반으로, 문제는 이러한 가정이 나중에 다루게 될 강화학습 문제 전반에 있어서, 강화학습 방법을 적용하는데 있어서 성립하지 않는다는 점

혹여 성립한다 하더라도 검증할 방법이 없음

이러한 방법을 적용했을 때 최적의 결과를 얻을 수 있고 손실이 어느정도 이상으로 커지지 않는다고 보장해 준다하더라도 방법이 가정하는 조건이 성립하지 않는다면 그림의 떡

 

활용과 탐험 사이의 균형을 맞추는 정교한 방법을 고안하는 문제는 다루지 않음

다중 선택 문제에서 활용과 탐험을 적절히 분배하는 여러가지 간단한 방법을 소개

그리고 ㅇ이 방법이 항상 활용만 하는 방법보다 훨씬 좋다는 것을 증명할 것

활용과 탐험을 적절히 분배해야 한다는 필요성은 강화학습에서만 나타나는 독특한 어려움

2.2 행동 가치 방법(action-value method)

행동의 가치를 추정하고 추정값으로부터 행동을 선택하도록 결정하는 방법

어떤 행동이 갖는 가치의 참값은 행동이 선택될 때의 평균 보상이라는 사실을 다시 상기

이 참값을 추정하는 자연스러운 방법은 실제로 받은 보상의 산술 평균을 계산하는 것

=>행동 가치 추정 방법은 관련 보상값에 대한 표본평균을 추정값으로 하기 때문에 표본 평균 방법이라고 부름

행동 가치를 추정하는 하나의 방법일 뿐이며 이 방법이 최선의 방법인 것은 아님 

 

가장 간단한 행동 선택 규칙은 추정가치가 최대인 행동 중 하나를 선택하는 것

탐욕적 행동 중 하나를 선택하는 것

탐욕적 행동이 여러 개 있다면 어떤 임의의 방법으로 , 아니면 그냥 무작위로 그 중 하나를 선택

탐욕적 행동 선택 방법

여기서  argmax는 바로 이어지는 수식의 값이 최대가 되도록 하는 행동 a를 나타냄(즉, 여러 개의 탐욕적 행동 중 선택은 임의)

탐욕적 행동을 선택하는 과정에는 즉각적인 보상을 최대화하기 위해 현재의 지식을 사용하는 것이 항상 포함

실제로는 더 좋은 결과를 낼 수 있을지도 모른다는 일말의 가능성을 확인하기 위해 누가 봐도 열등한 행동으로 표본을 구성하는 일은 탐욕적 행동 선택에서 결코 일어나지 않음

탐욕적 행동 선택을 대체할 만한 다른 대안은 대부분의 시간 동안에는 탐욕적 선택을 수행하고 상대적 빈도수 ε를 작은 값으로 유지하면서 탐욕적 선택 대신 모든 행동을 대상으로 무작위 선택, 이 때 모든 행동이 선택될 확률은 균등, 행동 선택은 행동 가치 추정과는 무관하게 이뤄짐

=>입실론 탐욕적 방법

장점 : 이후 단계의 개수가 무한으로 커지면 모든 행동이 선택되는 횟수가 무한이 됨

즉, Qt(a)가 q*(a)로 수렴이것은 최적의 행동을 선택할 확률이 1-  ε보다 큰 값으로, 거의 100%확률로 수렴한다는 뜻단점 : 위는 점근적 수렴성을 보장하는 것일 뿐, 실제 해당 방법의 효용성은 미지수

2.3 10중 선택 테스트

탐욕적 행동 사치 방법과 입실론 탐욕적 행동 가치 방법이 상대적으로 얼마나 효과적인지를 대략적으로 평가하기 위해 일련의 테스트용 문제로 두 방법을 수치적으로 비교