An Introduction to Sequential Decision-Making

The K-Armed Bandit Problem

Sequential Decision Making with Evaluative Feedback

• Sequential Decision Making에 대해 알아보자.

  • 신약 개발을 하는 의사의 입장에서 말이다.

• A, B, C 세 신약을 두고 테스트를 진행했다고 가정하자.

  • 이 중 C 약이 가장 환자들에게 유효하다는 것을 검증했다면 의사는 C 약의 효능을 높이 평가하게 될 것이다. (Reward up)

• K-armed bandit problem이란, agent가 "k"개의 선택지를 놓고 action을 취했을 때, 가장 효과가 좋은 경우의 수에게 reward를 주며 선택을 반복하는 일을 말한다.

  • 앞선 예시에서는 의사가 agent, 3개의 신약이 k actions, 선택지는 bandit(슬롯머신), 환자들의 반응은 reward라고 볼 수 있다.

• Action-Values function의 꼴은 아래와 같다.

  • 1부터 k개의 action을 취했을 때 나타나는 반응 reward의 기댓값이다.

    • 수식으로는 $q_{*}(a) \doteq E[R_t | A_t = a] = \displaystyle \sum_{r} p(r|a) r$로 적는다.

  • 이 때의 expected reward를 maximize하는 것이 목적인 함수이다.

• $q_{*}(a)$를 계산하는 과정은 아래와 같다.

  • 첫 번째 신약이 -11을 reward로 가질 확률이 0.5, 9를 reward로 가질 확률이 0.5라면 Expectation(기댓값)은 $0.5*-11 + 0.5*9 = -1$로 최종 R이 결정된다.

  • 두 번째 신약은 평균값이 1, 세 번째 신약은 평균값이 3으로 계산된다.

• Uncertainty(불확실성) 아래에서 무언가를 결정하는 일은 다음과 같은 상황 모두에서 적용될 수 있다.

  • 일상 생활 속 problem인 영화를 선택하는 일, 음악을 선택하는 일, 약을 선택하는 일, 음식을 선택하는 일처럼 말이다.

• Multi-Armed Bandits은 Reinforcement Learning에서 가장 기초적인 알고리즘인 알고리즘에 해당한다.

  • 여기에서 사용되는 기초 개념에는 actions, rawards, value functions이 있다.

Learning Action Values

• Action-Values function에 대해 알아보자.

  • 위에서 다룬 신약 개발 예제를 활용할 것이다.

• 이번 part가 끝난 이후 알게 될 개념들은 다음과 같다.

  • Sample-average method를 활용한 actino-values
  • Greedy action selection
  • Exploration-Exploitation 딜레마

• Action의 Value를 계산한다는 것은 expected reward를 계산한다는 것이다.

  • 그러나 $q_{*}(a)$를 명확하게 알 수가 없기 때문에 우리는 이를 추청할 뿐이다.

• Sample-Average Method는 아래와 같이 정의 된다.

  • 어떠한 action $a$에 대해 계산된 rewards를 모두 더해, 해당 action을 취하기 직전까지의 $t-1$ 시간으로 나눈 평균값이라고 할 수 있다.

    • 기호로는 $Q_t(a) = \displaystyle \frac{\sum_{i=1}^{t-1} R_i}{t-1}$로 표기한다.

• 만약 P, Y, B의 신약을 투여하여 효과를 본다면 reward는 1, 그렇지 않으면 0으로 주겠다고 설정해보자.

• 우리는 각 신약의 효능에 대한 확률을 아래와 같이 이미 알고 있다고 가정하겠다.

  • 그렇다면 의사는 어떻게 각 신약의 효능에 관한 확률 분포를 알아낼 수 있을까?

• 방법은 random하게 약을 처방하여 효능을 직접 추정하는 수밖에 없다.

  • 몇 번의 sample을 통한 실험을 진행하여, 누적된 reward를 시행 횟수로 나누어 평균 냄으로써 해결할 수 있다.

• Greedy한 selection이란, 이렇게 추정한 확률 중 가장 큰 확률을 가지는 action을 선택한다는 의미다.

  • 기호로는 $a_g = argmax Q(a)$로 표기한다.

• 요약하자면 다음과 같다.

  • Sample-average method로 action에 대한 values를 추정할 수 있다.
  • Greedy selection을 통해 확률이 가장 큰 action을 선택할 수 있다.

Estimating Action Values Incrementally

• Action Values를 Incremental하게 추정할 수 있는 방법에 대해 다뤄보자.

• 본 강의가 끝나고 나면 알게 될 내용들은 다음과 같다.

  • Sample-average method를 사용한 incremental update rule
  • Non-stationary bandit problem에 활용할 수 있는 general update rule

• 가치 함수($Q$)의 식은 보상($R$)의 평균이라 정의했다.

  • 이를 수식으로 나타내면 $Q_{n+1} = \displaystyle \sum_{i=1}^{n} R_i$라 표현할 수 있고, n-1에 대해 전개하면 $Q_{n+1} = \displaystyle \frac{1}{n} (R_n + \sum_{i=1}^{n-1} R_i)$다.

    $Q_{n+1} = \displaystyle \sum_{i=1}^{n} R_i = \displaystyle \frac{1}{n} (R_n + \sum_{i=1}^{n-1} R_i) = \displaystyle \frac{1}{n} (R_n + (n-1) \frac{1}{n-1} \sum_{i=1}^{n-1} R_i)$

    • 위 수식에서 $\frac{1}{n-1} \sum_{i=1}^{n-1} R_i$은 현재 state 직전의 가치 함수 $Q_n$이다.

• 위 수식을 직전 가치 함수 $Q_n$과 $R_n$으로만 다시 전개하면 다음과 같이 정리된다.

  • $Q_{n+1} = Q_n + \displaystyle \frac{1}{n} (R_n - Q_n)$

• 즉, 새로운 estimation은 {이전 estimation + step * (target - 이전 estimation)}으로 incremental하게 update 시킬 수 있다.

  • $\displaystyle \frac{1}{n}$은 몇 번의 step을 거쳐 reward를 얻었는지를 의미한다.

• General하게 표현하기 위해 step size는 $\alpha_n$으로 표기한다.

• $\alpha_n$은 [0, 1]사이의 parameter로 설정할 수 있는 것이다.

  • 이것이 Incremental이라 부르게 된 핵심 상수가 아닌가..

• Non-stationary bandit problem에서 $Q$함수를 업데이트하는 알고리즘 수식은 다음과 같다.

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

• 시행 횟수가 많아질 수록 $n$의 크기가 커진다.

  • 이는 Reward에 곱해지는 weight에 곱해지는 $\alpha$가 점차 작아지는 것을 뜻하며, 가치 함수가 특정 값으로 수렴하여 update가 점점 느려지는 것을 뜻한다. → Incremental

• 위 함수를 새롭게 전개하여 여러 시행 횟수의 급수로 표현해보자.

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

    $= \alpha R_n + Q_n - \alpha Q_n = \alpha R_n + (1- \alpha) Q_n$

    $= \alpha R_n + (1- \alpha) [\alpha R_{n-1} + (1-\alpha)Q_{n-1}]$

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

• 이를 initial action-value $Q_i$까지 전개해보면 아래와 같은 수식으로 정리된다.

  • $Q_{n+1} = (1- \alpha)^n Q_i + \displaystyle \sum_{i=1}^{n} \alpha (1- \alpha)^{n+1} R_i$

• 요점은 다음과 같다.

  • Sample-average method를 통해 incremental update rule을 유도할 수 있다.
  • Constant stepsize parameter로부터 non-stationary bandit problem을 유도할 수 있다.

Exploration vs. Exploitation Tradeoff

What is the trade-off?

• 만약 친구와 함께 restaurant를 가야하는 상황이라고 가정해보자.

  • 매일 가는 맛있는 음식을 먹을 수도 있지만, 새로운 곳을 도전해볼 수도 있는 상황이기도 하다.

    • 두 가지 조건을 모두 만족시킬 수 있는 선택지가 존재할까?

• 이번 강의를 통해 알게 될 개념들은 다음과 같다.

  • Exploration-Exploitation trade-off
  • Epsilon greedy method

• Exploration 탐색은 long-term benefit을 향상시키기 위한 action을 취하는 방법론이다.

  • 각 조건들의 의미를 보고 음식을 선택해 나가보자.

    • $q(a)$ : estimated value for picking that meal
      $N(a)$ : number of times you have picked that meal
      $q_*(a)$ : value of each meal

• $q_*(a)$는 각 식당의 평점 기댓값, $q(a)$는 시행 횟수 n과 reward로부터 계산된 추정 평점 기대치에 해당한다.

  • 각 식당에 대한 평가는 매번 동일하지 않을 것이다.

    • 이전 기대치에서 현재 주게 되는 기대치들이 합산되어 계속 쌓인다고 보면 된다.

• Exploitation 탐색은 short-term benefit을 향상시키기 위한 action을 취하는 방법론이다.

• 식당의 평점이 가장 높은 곳만을 찾다 보면 주변에 더 좋은 식당이 있는 상황이더라도 가보지 못할 경우들이 생긴다.

  • 자신이 경험해 본 선택지들 중에서만 고를 수 있으므로, "never discoverd best action"인 상황이 생길지도 모른다.

• 그렇다면 어떻게 이것들을 balance있게 선택할 수 있을까?

• 우리가 주사위를 던지는 상황을 가정한다면 random하게 한 번 굴렸을 때 1이 나올 수 있는 확률은 $\displaystyle \frac{1}{6}$이다.

  • 만약 주사위를 굴려 1이 나왔음에도 다른 선택지들을 향해 간다면, Greedy한 선택을 하고 있는 상황일 것이다.

    • Random한 상황은 1/6, Greedy한 선택은 5/6다.

• 이러한 선택 방법론을 epsilon-greedy action selection이라 한다.

  • 확률이 $\epsilon$일 경우에 random 선택하도록 하고, $1-\epsilon$일 경우에 argmax(greedy) 선택하는 방법론이다.

    • 이러한 상황이라면 exploration과 exploitation을 균형있게 활용하는 방법이 될 수 있다.

• 10-armed bandits problem으로 다시 넘어와서, 각 선택지의 기댓값을 Normal distribution으로 가정해보자.

• 1번의 시행으로는 noisy curve가 매우 많이 생기는 것을 알 수 있다.

  • 두 번째 그림은 2번, 3번 시행했을 때의 curve를 나타낸다.

• 시행 횟수를 20, 2000번으로 늘려가보면, 점점 noise가 줄어드는 것을 알 수 있다.

• 우리는 random 시행에 대한 확률을 의미하는 $\epsilon$을 parameter로 취급하여 조정함으로써 다른 결과를 얻어낼 수 있다.

  • $\epsilon$이 0이라면 greedy한 선택만을 택하는 것이다(exploitation).

    • $\epsilon$이 커질수록 exploration 비율을 높이는 것이라 할 수 있다.

• 요약하자면 exploration과 exploitation은 tradeoff한 관계를 가지며, epsilon-greedy 선택 알고리즘을 통해 두 비중을 balance하게 맞출 수 있다.

Optimistic Initial Values

• 만일 의사가 매우 낙관적인 성향이어서 처방한 value 값이 다소 큰 값이라면 어떨까?

  • 놀랍게도 optimistic initial values는 exploration과 exploitation의 균형을 맞추는 효과적인 방법이기도 하다.

• 이번 강의에서는 optimistic initial values에 대해 알아보도록 하자.

  • 추가로 optimistic initial values method의 몇 가지 한계점에 대해서도 다루려 한다.

• 이전에는 초깃값을 0으로 두고 임상실험을 진행하였었다.

  • 이는 낙관적인(optimistic) 초깃값을 사용하는 경우가 아니다.

• 각 시험체의 initial estimated value를 2.0으로 설정하였다고 해보자. (optimistic)

  • 그리고 항상 greedy한 선택을 반복하였다고 가정해 보겠다.

• $\alpha$를 0.5로 설정하여 치료약을 random하게 선택한 뒤, 처방한 약에 대한 reward를 1 or 0으로 주었다고 하자.

  • 초깃값(2)에 비해 reward(1)가 더 적기 때문에 estimated values는 초반에는 급격하게 감소한다.

    • 그리고 계속해서 greedy한 선택으로 B 선택지까지 처방한 결과가 아래와 같다.

• 여러 번의 시행으로 각 선택지의 values는 점점 특정한 값으로 수렴해 갈 것이다.

  • 중요한 점은 초깃값이 낙관적으로 설정된 경우에 초반 몇 번의 탐색은 여러 개의 선택지를 모두 선택하는 방향으로 흘러간다는 것이다.

    • Initial value 보다 받는 reward가 처음엔 적은 값이기 때문에, greedy한 선택 시 다른 선택지를 더 살펴보고 흘러가기 때문이다.

• 다시 10-armed bandit problem으로 넘어가보자.

  • 현재 대부분의 values는 3 이하에 위치해 있다.

    • 이 때, Initial value를 optimistic하게 줘서 5로 설정한다면 초반 몇 번의 시행 동안은 다른 선택지들이 더 매력적으로 느껴져 exploration할 수 있게 된다.

• 아래 기존 epsilon-greedy 탐색 방식과 optimistic greedy 탐색 방식의 차이를 보도록 하자.

  • Epsilon-greedy에 비해 optimistic greedy 방식이 수렴 속도가 훨씬 빠른 것을 알 수 있다.(x축)

    • washes out more samples : 탐색이 줄어듦

• 그러나 optimistic initial values가 항상 좋은 방법인 것만은 아니다.

  1. 학습 초반에만 급격한 탐색이 가능하며
  2. Non-stationary problem에는 적합하지 않을 수 있고
  3. 실제로는 최대 보상을 알지 못하기 때문에 어떤 값이 optimistic한 값인지 알 수 없을지도 모른다.

• Summary

Upper-Confidence Bound (UCB) Action Selection

• UCB action selection은 추정의 불확실성(uncertainty)을 이용하는 방법론이다.

  • 우리는 sampling 된 보상을 바탕으로 value를 추정하기 때문에 정확성 속에는 항상 uncertainty가 포함되어 있을 수밖에 없다.

• 이번 강의에서는 Upper-Confidence Bound action에 대해 알아보자.

• Epsilon-greedy 알고리즘을 다시 한 번 살펴보자.

  • Uniform 분포에서 random한 선택지를 고르는 방법을 좀 더 향상시킬 수 있는 방법이 있을까?

• $Q(a)$는 현재 추정한 value이며 괄호는 $Q$ 주위의 신뢰 구간을 나타낸다.

  • $q_*(a)$는 신뢰 구간 안에 어디든 존재할 수 있다.

• $Q(a)$의 신뢰 구간의 최대치는 lower bound와 upper bound로 나뉜다.

• 중간 부분은 불확실성을 나타내는 신뢰 구간(confidence interval)이라 할 수 있다.

• 추정한 가치의 신뢰 구간 면적에 따라 uncertainty의 정도도 결정된다.

  • 면적이 좁다면 불확실성이 적고, 면적이 넓으면 불확실성도 크다.

• 만약 불확실성이 동반되는 세 가지 행동이 있다고 가정해, 한 가지 action을 수행했다고 생각해보자.

  • Agent는 어느 것이 최선의 선택인지 모른 채로 무조건 greedy한 선택지를 골라 왔다.

    • 각 state의 lower bound와 upper bound가 주어진다면, 잘 알지 못하는 action에 대해서도 배울 수 있기 때문에 의미를 가진다.

• Upper-Confidence Bound 값을 사용하려면 아래와 같은 수식으로 선택하게 된다.

  • 왼쪽 항이 exploit한 항이며 오른쪽 항의 explore한 항이다.

• $\displaystyle c \sqrt{\frac{ln t}{N_t(a)}}$ 항의 의미는 다음과 같다.

  • 전체 timesteps를 action $a$가 선택된 횟수로 나누어 표현한다.

  • 이는 특정 action을 많이 선택하면 할수록 uncertainty가 줄어드는 것을 의미한다고 볼 수 있다.

    • 따라서 신뢰 구간이 매우 좁아진다.

• Epsilon-greedy 알고리즘을 사용하는 것보다 UCB 알고리즘을 사용할 때, 조금 더 성능이 향상되는 것을 보여주는 그래프다.

• Summary

---

• 출처 : [Coursera] Reinforcement Learning Specialization