밴디트 문제 bandit problem

밴디트=슬롯 머신

여러대의 슬롯머신이 줄줄이 있다.

 

multi-armed bandit problem

• agent : player
• slot machine : environment
• player would be interaction with slot machine.
  • this is basic frame of reinforcement learning.
• action : play가 여러대의 slot machine중에서 하나를 선택한다.
• reward : coin ( 플레이어가 선택한 slot machine으로부터 coin을 얻음)

 

위의 문제에서 목표는?

• coin을 최대한 많이 얻어야하며, 그러기 위해서는 승률이 좋은 slot machine을 선택해야함.

 

let, define 슬롯머신 a,b의 확률 분포표

얻을 수 있는 동전 수	0.	1	5	10
확률(  machine A)	0.70	0.15	0.12	0.03

 

얻을 수 있는 동전 수	0.	1	5	10
확률( machine B)	0.50	0.40	0.09	0.01

• slot machine a의 기대값 ( expectation value )
  • (0 x 0.70) + (1 x 0.15 ) + (5 x 0.12 ) + (10 x 0.03 ) = 1.05
• slot machine a의 기대값 ( expectation value )
  • (0 x 0.50) + (1 x 0.40 ) + (5 x 0.09 ) + (10 x 0.01 ) = 0.95
• 위의 두 값은 슬롯머신 a,b의 가치 or a,b의 행동 가치라고 함.

 

q(A) = E [ R | A ]

• R ( reward ) -> 보상 -> 코인 갯수
• A ( action ) -> agent가 하는 행동 -> a,b중에 하나를 고르는 행동
• E ( expectation ) -> 기대값 -> 행동 A를 하였을때 얻는 보상 기대값
• q ( quality ) -> 행동가치
  • 소문자 q를 사용하는 경우에는 '실제 행동 가치'를 의미한다.
  • 대문자 Q를 사용하는 경우는 '실제 행동 가치의 추정치'이다.
  • ex) A슬롯머신...
    • 총 3번을 수행하였고 얻은 코인은 0,1,5이다..
      그러면 Q(a) = 2이다.
  • ex) B슬롯머신..
    • 총 3번을 수행하고, 얻은 코인은 1,0,0이다.
      그러면 Q(b)= 1/3 = 0.33333이다.
  • 위의 2 예제를 통해서 슬롯머신 a가 실제 가치가 좀 더 높음을 추정한다.

슬롯머신의 평균을 구하는 코드

 

 

하지만 위의 과정은 비효율적이다....

=> 왜냐하면 n이 커질수록, rewards의 합을 매번 구해야하기 때문이다. 즉, 이로 인해 계산 비용이 증가한다.

==> 아래는 좀 더 효율적으로 하기 위한 전개이다.

• 위에서 보면 Q의 n-1에서 n으로  생신될때, Rn - Qn-1의 길이에 1/n을 곱한 값만큼 이동한다.
  ( 왜냐하면 Qn-1은 R1부터 Rn-1의 합의 n-1을 나눈거다. 그래서 Qn-1에서 다음 Reward를 얻으면 앞으로 나아가는거고...)
  ( Qn은 그로 인해서 당연 Rn의 뒤에 있어야한다. )
• 위의 그래프를 보면 Qn이 Rn방향으로 진행되기 위해서는 1/n이 결정한다.
  즉 ,1/n이 갱신되는 양을 조절하니 학습률learning rate의 역할을 한다.
• 시도 횟수 n이 늘어날수록 1/n의 값은 작아지며, 이는 Qn의 생신되는 양이 작아짐을 의미.

위와 같이 코드를 개선할 수 있다. 위와 같은 구현을 증분 구현이라고 한다.

 

---

 

슬롯 머신에서의 탐욕 정책

• agent가 각각의 머신을 해보고, 가치 추정치가 가장 높은 슬롯 머신을 선택하는것
• 단점
  • 만약, 한번씩한 플레이 한 경우 불확실하다.
• 활용 exploitation
  • 현재까지 agent가 play한 결과를 가지고, 가치 추정치가 가장 높은 것을 선택하는것
• 탐색 exploration
  • 슬롯 머신의 가치를 정확히 추정하기 위해서 여러 머신을 시도
• 위의 활용과 탐색은 서로 상충되니, 하나를 선택하면 하나는 못한다.
  • 한 번의 시도만으로 좋은 결과를 얻고 싶으면 활용을 선택하나, 장기적으로 좋은 결과를 위해서는 탐색을 해야한다.
    ===> 강화학습은 '활용과 탐색'의 균형이 중요

 

 

 ε -greedy 정책

• 활용과 탐색의 균형을 맞추기 위한 알고리즘
• ε = 0.x 의 확률로 탐색을 하고, 나머지는 활용( ε -0.x)하는 방식.
  • 현재까지 얻은 경험을 '활용'하며, 가끔식 greedy하지 못한 행동을 함으로써 더 좋은 행동이 있는지 '탐색'한다.
• 탐색할때는 다음의 행동을 무작위로 수행한다. 이렇게 하여 가능한 모든 행동의 가치 추정치의 신뢰도를 높힌다.