[수정중][David Silver L2] Markov Decision Process

알파고 만드신 데이비드 실버(David Silver)님의 강의 자료를 정리한 내용입니다

웹사이트 :https://www.davidsilver.uk/

영상 : https://www.youtube.com/watch?v=lfHX2hHRMVQ&t=217s&ab_channel=DeepMind

---

Markov Processes

• MarkovDecisionProcesses
  • environment가 온전히 관찰 가능할 때 강화학습의 environment를 일컫는다.
  • 현재 state는 process를 완전히 특징짓는다.
  • 대부분의 모든 강화학습 문제는 MDPs 될 수 있다.
    • 최적 컨트롤은 연속적 MDPs 로 처리함
    • 부분 관찰가능한 문제는 MDPs로 전환 가능함
    • Bandits는 하나의 state인 MDPs 임
• MarkovProperty
  • MarkovProperty
    • 미래는 지나간 과거로부터 독립적이다.
    • $ \mathbb{P}[S_{t+1}|S_{t}] = \mathbb{P}[S_{t+1}|S_{1}, ..., S_{t}] $ 일 경우에만 $state S_{t}$는 Markov 다.
    • state 는 history로부터 모든 관련된 정보를 갖고 있다.
    • state가 알려지면, history는 버려질 수도 (state는 미래의 sufficient한 통계)
  • StateTransitionMatrix
    • a Markov state $s$, 다음 state $s'$, state 전이 확률(transition probability)는 다음과 같다.
      $ \mathcal{P}_ss' = \mathbb{P} [S_{t+1} = s'|S_{t} = s] $
    • state 전이 메트릭스 $ \mathcal{P}$는 전이 확률을 다음과 같이 나타낸다. 각 row를 더하면 1이 된다.

• Markov Chains
  • Markov Chains (= Markov Process)
    • 동떨어진(memoryless) 랜덤 프로세스.
    • tuple $<\mathcal{S},\mathcal{P}>$
      $ \mathcal{S}$ : 한정된 state 세트, $ \mathcal{P}$ : state 전이확률 메트릭스
    • 학생의 Markov Chain 예시:

Markov Reward Processes

• MarkovRewardProcesses
  • Markov Reward Processes : Markov chain with values
    tuple $<\mathcal{S},\mathcal{P},\mathcal{R},\mathcal{\gamma}>$
    $ \mathcal{R}$ : 보상함수 $ \mathcal{R}_{s} = \mathbb{E}[R_{t+1}|S_{t} = s][$
    $ \mathcal{\gamma}$: 0과 1 사이의 discount factor
  • 학생의 MRP 예시:

• Return
  • return $G_{t}$ 는 time step $t$ 에서의 총 discount reward
    $G_{t} = R_{t+1} + \gamma R_{t+2} + ... = \sum_{k=0}^{\infty}\gamma^{k}R_{t+k_1}$
    • discount $ \gamma \in [0,1] $ : 미래 보상의 현재 가치
    • K+1 time-steps 이후 받는 보상 R의 가치: $ \gamma^k R$
    • $ \gamma$ 가 0 가까우면 근시적 평가(myopic) , 1에 가까우면 원시적 평가(far-sighted)
  • discount 하는 이유:
    • 수리적 편리함
    • 무한반복을 피하기 위해
    • 미래의 불확실성이 다 드러나지 않을 수 있음
    • 금융쪽에서 즉각적인 이자가 delay된 보상보다 클 수 있음
    • 사람은 즉각적인 보상에 선호도를 보임
    • 모든 시퀀스가 terminate 하면 undiscounted Markov Reward Processes ($ \gamma = 1$) 가능 할 수도
• Value Function
  • state value function ($v(s)$) : state $s$의 장기 value 줌. state s에서 기대 보상.
    $v(s) = \mathbb{E}[G_t|S_t=s] $
  • 학생 MRP return 예시:

• Bellman Equation
  • value function 은 두 부분으로 나눌 수 있다
    
    • 즉각적인 보상 $R+{t+1}$
    • 후속 state의 discount value $ \gamma v(S+{t+1})$

• • 다음과 같이 나타낼 수 있다.
    • $V(s) = \mathbb{E}[R_{t+1}+\gamma v(S_{t+1}) | S_t = s] $
    • $V(s) = \mathcal{R_s} + \gamma \sum_{s' \in S} {\mathcal P_{ss'}v(s')} $
  • v가 state별 하나의 entry의 column vector 일 때, $v =\mathcal{R}+ \gamma\mathcal{P}v$

1. • Bellman equation 는 linear equation
   • Computational complexity : $O(n^3)$
   • 작은 MRPs 에서는direct solution 사용 가능

• 큰 MRPs 위한 많은 방법들이 있음
  • Dynamic programming (진행했던 연산 값을저장해두었다가재사용)
  • 몬테카를로 (랜덤 샘플 학습)
  • Temporal-Difference learning (시간차 학습, 위의 두개를 합친것)

 

 

 

여기까지는 모두 다음 내용을 설명하기 위한 부분이었습니다. 같이 배워보시죠.

 

MarkovDecisionProcesses

• MarkovDecisionProcesses
  • Markov reward process with decisions. 모든 state가 Markov인 환경.
  • tuple $<\mathcal{S,A,P,R,\gamma}>$
    • $ \mathcal{S}$ : 한정된 state set
    • $ \mathcal{A}$ : 한정된 action set
    • $ \mathcal{P}$ : state transition 확률 메트릭스
      $ \mathcal{P}_{ss'}^a = \mathbb{P}[S_{t+1} = s' | S_t = s, A_t = a] $
    • $ \mathcal{R}$ : 보상 함수
      $ \mathcal{R}_s^a = \mathbb{E}[R_{t+1} | S_t = s, A_t = a] $
    • $ \gamma $ : discount factor