바닥부터 배우는 강화학습 <독서록>

개요

도서명 : 바닥부터 배우는 강화학습
저자 : 노승은
출판사 : 영진 닷컴

딥러닝에 대한 프로젝트 과목인 오픈소스소프트웨어프로젝트2 의 민덕기 교수님 추천으로 공부하게 되었다.

이 책을 통해 기계학습에 대한 기초적인 이해를 할 수 있길 바라며, 내가 앞으로 진행할 분야(지금은 잠정적으로 자연어 처리)를 정할 수 있게되길 바란다.

독서록으로 자유로운 감상, 궁금한 점을 기록할 것이다.

메모

MDP

• MDP의 구성

  (S,A,P,R,$\gamma$)

  S: 상태의 집합
  A: 액션의 집합
  P: 전이 확률 행렬
  R: 보상 함수
  $\gamma$: 감쇠 인자

  이들(특히 보상함수 와 전이확률행렬)을 알 때
  MDP를 안다 라고 표현 MDP를 안다 = 모델을 안다. MDP를 모른다 = 모델 프리다

• 용어

  • Return과 Reward

    Reward는 어떤 상태에 도달했을 때 얻을 수 있는 것.
    Return은 현재 상태에서 종료까지 얻을 수 있는 Reward 에 감쇄인자를 곱한 값.

  • 전이 확률 행렬 $\mathrm{P}^{a}_{ss’}$

    현재 상태가 s이며 에이전트가 a라는 행동을 취했을 때, 다음 상태가 s’가 될 확률

  • 보상(reward)함수 $\mathrm{R}^{a}_{s}$

    상태 s에서 에이전트가 a라는 행동을 했을 때 받을 수 있는 보상의 기댓값.

  • 정책함수(policy function) $\pi \left( \mathrm{a} \mid \mathrm{s} \right) = \mathbb{P} \left[ \mathrm{A}_t = a \mid \mathrm{S}_t = \mathrm{s} \right] $

    에이전트의 행동지침
    상태 s에서 에이전트가 action a를 취할 확률

  • 상태 가치 함수 (state value function)
    \(\begin{matrix} v_{\pi} (s) &=& \mathbb{E}_{\pi} \left[ r_{t+1} + \gamma{r}_{t+2} + \gamma^2r_{t+3} + ... \mid \mathrm{S}_t = s\right] \\ &=& \mathbb{E}_{\pi} \left[ \mathrm{G}_t \mid \mathrm{S}_t = s\right] \end{matrix}\)

    어떤 상태 s에서 미래에 얻을 리턴의 기댓값

  • 상태-액션 가치 함수 (state-action value function)
    \(q_{\pi}(\mathrm{s}, \mathrm{a}) = \mathbb{E}_{\pi} \left[\mathrm{G}_t \mid \mathrm{S}_t = s, \mathrm{A}_t = a\right]\)

    어떤 상태 s에서 에이전트가 a라는 행동을 취했을 때, 얻을 리턴의 기댓값 (단, a 이후에도 $\pi$에 따라 행동을 결정)

  • MDP 를 푼다는 것

    $\pi^, v^$ 를 찾는 것. (최적 정책, 최적 가치 함수)

    • 최적 밸류

      $v_*(\mathrm{s}) = \max_\pi v_\pi(\mathrm{s})$
      최적의 정책을 수행할 경우 어떤 상태의 가치

      $q_*(\mathrm{s, a}) = \max_\pi q_\pi(\mathrm{s, a})$
      최적의 정책을 수행할 경우 어떤 상태에서 어떤 액션을 취하는 것의 가치

벨만 방정식

• 벨만 기대 방정식

  • 0 단계
    \(v_{\pi}(\mathrm{s}_t) = \mathbb{E}_{\pi}\left[r_{t+1} + \gamma{v}_{\pi}(s_{t+1})\right]\)
    \(q_{\pi}(\mathrm{s}_t, \mathrm{a}_t) = \mathbb{E}_{\pi}\left[r_{t+1} + \gamma{q}_{\pi}(s_{t+1}, a_{t+1})\right]\)

  • 1 단계
    \(v_{\pi}(s) = \sum_{a \in A} \pi(a \mid s)q_{\pi}(s , a)\)
    \(q_{\pi}(s , a) = r_s^a + \gamma \sum_{s' \in \mathrm{S}}P^a_{s s'}v_{\pi}(s')\)

  • 2단계
    \(v_{\pi}(s) = \sum_{a \in \mathrm{A}} \{\pi(a \mid s)\} \times \left( r_s^a + \gamma \sum_{s' \in S}\{P_{s s'}^a v_{\pi}(s')\} \right)\)
    \(q_{\pi}(s , a) = r_s^a + \gamma \sum_{s' \in S} P_{s s'}^a \times\sum_{a \in A}\{ \pi(a' \mid s') q_{\pi}(s', a') \}\)

• 벨만 최적 방정식

  • 0 단계
    \(v_*(\mathrm{s}_t) = \max_a\mathbb{E}\left[r_{t+1} + \gamma{v}_{*}(s_{t+1})\right]\)
    \(q_{*}(\mathrm{s}_t, \mathrm{a}_t) = \mathbb{E}_{\pi}\left[r_{t+1} + \gamma \max_{a'} q_{*}(s_{t+1}, a')\right]\)

  • 1 단계
    \(v_{*}(s) = \max_{a} q_{*}(s, a)\)
    \(q_{*}(s , a) = r_s^a + \gamma \sum_{s' \in \mathrm{S}}P^a_{s s'}v_{*}(s')\)

  • 2단계
    \(v_{*}(s) = \max_a \left[ r_s^a + \gamma \sum_{s' \in S}\{P_{s s'}^a v_{*}(s')\} \right]\)
    \(q_{*}(s , a) = r_s^a + \gamma \sum_{s' \in S}\left\{ P_{s s'}^a \max_{a'} q_{*}(s', a')\right\}\)

MDP를 알 때 MDP를 푸는 방법

MDP를 알 때 MDP를 푸는 것을 플래닝이라고 한다.
직접 데이터를 모으러 뛰어다니지 않고, 알고 있는 보상함수와 전이확률행렬을 이용해 시뮬레이션을 통해 최적의 정책 * 를 찾는 것

• 이론적 배경

  \[v_{\pi}(s) = \sum_{a \in \mathrm{A}} \{\pi(a \mid s)\} \times \left( r_s^a + \gamma \sum_{s' \in S}\{P_{s s'}^a v_{\pi}(s')\} \right)\]

  벨만 기대 방정식: 2단계

• policy iteration

• value iteration

MDP를 모를 때 최고의 정책을 찾기

1. MDP를 모를 때 밸류를 평가하기

   • Monte Carlo method

     \[v_\pi(\mathrm{s}_t) = \mathbb{E}_\pi \left[G_t \right]\]

     어떤 상태의 가치는 그 상태에서 가능한 리턴의 기댓값이다.
     기댓값은 모든 리턴을 표본으로 만들어져야 하지만, 실제로 모든 리턴을 알아내기는 어렵다.
     여러개의 리턴 값들을 평균낸다면 원하는 값에 근사한 값을 얻을 수 있을 것이다.

     • $\mathrm{N}(s)$

       상태 s를 총 몇 번 방문했는 지에 대한 값

     • $\mathrm{V}(s)$

       해당 상태에서 경험했던 리턴의 총합에 대한 값

     상태 $s_0$ 에서 액션 $a_0$ 를 취해 $r_0$ 의 리워드를 받고, 상태 $s_1$ 에 도달한다.

     \[\mathrm{s}_0, a_0, r_1, \mathrm{s}_1, a_1, r_2, \mathrm{s}_2, ... , a_{T-1}, r_{T}, \mathrm{s}_T\]

     이 에피소드를 가지고, 거쳐왔던 모든 상태들의 V(s)와 N(s)를 업데이트 한다.

     중요!!! 여기서 \(\mathrm{s}_0\) 는 에피소드 순서상 첫번째 상태를 의미하고,
     상태공간의 상태 \(s_0\) 와는 구별된다.
     상태 \(\mathrm{s}_0\) 가 상태 공간의 \(s_x\) 에 대응되고
     \(\mathrm{s}_0\)에서 에피소드 리턴을 \(G_0\) 라고 할 때, \(\left(G_0 = r_1 + \gamma{r}_2+ ... \gamma^{T-1}r_{T}\right)\)

     $N(s_x) \leftarrow N(s_x) + 1$

     $V(s_x) \leftarrow V(s_t) + G_t$

     으로 값을 업데이트 해준다.

     충분한 에피소드를 이용해 $\mathrm{N}(s_x) \mathrm{V}(s_x)$ 를 업데이트 했다면.

     \[v_\pi(s_x) \cong \frac{\mathrm{V}(s_x)}{\mathrm{N}(s_x)}\]

     ---

     • 업데이트 과정을 변형한 버전

       \[\mathrm{V}(s_x) \leftarrow (1 - a) * \mathrm{V}(s_x) + a * G_x\]

       $a$ 를 0.1이라고 할 때 90%의 기존값에 10%의 새로운 에피소드 리턴을 더하는 식으로 업데이트 한다.

   ---

   • Temporal Difference method

     MC 에서는 리턴을 가지고 학습하기에 종료상태까지 진행해야 한다는 단점이 있다.
     TD 는 종료상태까지 진행하지 않고도 벨류를 업데이트 할 수 있는 방법론이다.

     \(v_{\pi}(\mathrm{s}_t) = \mathbb{E}_{\pi}\left[r_{t+1} + \gamma{v}_{\pi}(s_{t+1})\right]\)
     이 이론적 배경이다. (벨만 기대 방정식: 0단계)

     \(r_{t+1} + \gamma{v}_{\pi}(s_{t+1})\) 를 TD target 이라고 명명하고, TD target을 여러번 뽑아서 평균을 내어 목표값에 다가간다.

     TD target의 구성인 \({v}_{\pi}(s_{t+1})\) 를 알기 위해선 \(s_{t+1}\) 가 무엇인지 알아야 하고, 이는 한 스탭을 진행하여 확정지을 수 있다.
     비록 정확한 \({v}_{\pi}(s_{t+1})\) 값을 알 수는 없지만, 지금까지 업데이트 해온 상태-벨류 테이블을 검색해 알고 있는 최선의 \({v}_{\pi}(s_{t+1})\) 를 알 수 있다.
     여기에 $\gamma$를 곱하고 스텝의 결과로 받은 $r_{t+1}$ 값을 더한다면 TD target 이 완성된다!

2. MDP를 모를 때, MC 를 이용해 정책을 만들기

   MDP 를 알 때 정책 평가 -> 정책 개선(greedy) 식으로 최고의 정책을 찾았다.
   => 이걸 좀 변형한다면 MDP를 몰라도 최고의 정책을 만드는 방법이 있다.

   그러나 지금은 \(r_s^a, P_{s s'}^a\) 를 모르는 상태이기 때문에 실제로 환경에서 액션을 해야 하는 상황이다. policy evaluation의 이론적 배경인 벨만 방정식: 2단계 를 사용할 수 없다.
   => MC 를 이용한다면 MDP를 몰라도 상태-액션 가치 함수(q(s, a))를 알 수 있다. (ch5에서는 v(s)를 찾았지만, q(s, a)도 알 수 있다.)

   policy improvement의 그리디를 사용할 수 없다. 어떤 상태 s 에서 a 라는 액션을 취할 때 다음 상태에 대한 정보를 모르기 때문에 s 에서 액션을 선택하는 것의 리턴 기댓값을 알지 못한다. 따라서 가장 기댓값이 높은 액션을 취하는 그리디 정책도 불가능하다.
   => MC 를 이용해 q(s, a) 를 바로 구할 수 있기 때문에 어떤 상태에서 어떤 액션을 취할지에 대한 greedy 정책을 수행하는 것이 수월하다.

   • 추가적인 장치: 입실론 $\epsilon$

     만약 상태-액션 가치함수를 0으로 초기화 하고, 처음 정책 evaluation을 해서 어떤 q(s, a)가 양의 값이 나왔다고 할 경우 상태 s에선 앞으로 a만 선택하게 된다. 처음에 갔던 길만 계속 가는 정책이 만들어져버린다. 이를 방지하기 위해 랜덤적인 요소를 가미한다.

     그것이 바로 입실론 $\epsilon$ 이다. max( q(s, a) ) 가 아닌 다른 a’을 $\epsilon$ 만큼 선택하는 policy improvement 을 수행하는 것이다.

     이를 $\epsilon$ - greedy 라고 한다.

     여기서 그치지 않는다. 아직 정책이 미숙할 때는 여러가지 액션들을 탐색하도록 하고, 점 점 성숙해질 수록 $\epsilon$ 을 줄여가는 정책을 수행하는게 더 좋을 것이다. 이를 decaying $\epsilon$ - greedy 라고 한다.

   ---

   정리하자면,

   • policy evaluation

     MC 를 이용해 q(s, a) 구하기

   • policy improvement

     decaying $\epsilon$ - greedy 를 더이상 정책의 변화가 없을 때 까지 반복한다.

3. MDP를 모를 때, TD 를 이용해 정책을 만들기

이해가 잘 안 됐던 부분

• CH2

  • MRP (Markov Reward Process) 에서 감쇠 인자 $\gamma$ 의 필요성

    3가지 근거를 들어 $\gamma$ 의 필요성을 주장한다.
    1. 수학적 편리성 - 리턴이 무한한 값을 가질 수 없도록 제어
    2. 사람의 선호 반영 - 미래에 있을 효익에 대한 현재 가치로의 할인 (시간 가치)
    3. 미래의 불확실성 반영 - (2와 동일한 이유로 보임)

    우리가 기계에게 원하는 것은 좋은 결과일 것이다. 과정이야 어떻든 최대의 리턴을 추구하면 되는데 감쇠 인자를 곱한다는 것은 미래 가치에 대한 축소이다.
    2와 3은 따라서 학습자가 고려할 사항이 아니다. 사람이 아닐뿐더러 시뮬레이션은 불확실성을 고려할 필요가 없다.
    1은 이해는 간다. 그러나 한편으론 무진장 많은 경우의 수더라도 유한한 값일텐데, 자료형 등 현실적 연산 한계를 고려한 것일까? 근시안적으로 접근하면 local optima 에 빠지지 않을까?
    아무튼 이상적으론 감쇠 인자가 없는게 좋은 결과를 가져올 것 같다는 생각이 든다.

• CH4

  • multi modal 의 상황에도 가능한가?

    random move 라는 최초 정책으로부터 state-value 테이블을 업데이트 하며 greedy 로 최고의 정책을 찾을 수 있었다.

    근데 이거 매우 특수한 조건인 것 같다는 생각이 든다.

    random move 가 아니라 random 하지 않고 이상한 경향을 갖는 최초 정책이었다면?

    지금처럼 하나의 종료 상태로 점철되지 않고, 여러가지 종료상태가 있고, 여러가지 해가 있다면?

• CH6

  • 논리적 오류?

    전이확률행렬을 모르기 때문에 다음 state이 무엇인지 모르고, 이로 인해 현제 state에서 취할 action을 고르는 greedy 정책을 수립할 수 없다.
    => 동의한다.

    상태-액션 가치 함수 q(s, a)를 사용하여 이를 극복한다? 몬테 카를로로 알 수 있는 것은 상태 가치 함수 이다. 전이확률행렬 없이는 v(s)로 부터 q(s, a)를 산출 할 수 없는데…?

    이어서 나오는 설명을 보니 MC 에서 q(s, a)를 찾는 것이라고 한다. ch5에서는 상태를 찾는다고 했는데…