1. MDP - Markov Decision Process

이두현·2022년 2월 9일
0

MDP 가정

  • environment가 fully observable 하다

  • Machine의 state는 markov property 를 갖는다
    P[St+1St]=P[St+1S1,...,St]P[S_{t+1}|S_t]=P[S_{t+1}|S_1,...,S_t]
    즉, 이전 state에 상관없이 바로 직전 state에만 영향을 받는다.

  • Markov Process는 set of finite state인 S와 state transition probability matrix P의 튜플을 의미한다.
    State transition matrix는 아래와 같은 식을 의미하며 PssP_{ss'}은 state s에서 s'으로 갈 확률을 의미한다.
    P=[P11...P1nPn1...Pnn]P=\begin{bmatrix} P_{11} &...&P_{1n} \\ \vdots \\P_{n1} & ... & P_{nn} \end{bmatrix}
    그리고 이 때 각 행의 합은 1이다.

Markov Reward Process

  • 위의 Markov Process에 Reward 개념을 더한 process를 의미한다.
    Rs=E[Rt+1St=s]R_s=E[R_{t+1}|S_t=s] 이고 현재 시간에 대한 reward이지만 시간은 t+1임에 유의하자

  • Return GtG_t는 아래와 같이 정의되고 γ\gamma는 discount factor로 미래에 얻는 수익은 감산하여 취급된다고 이해하면 된다 (금전적인 보상의 경우 이율을 의미할 수 있고 생명체가 얻는 보상의 경우 현재 이득을 더욱 값지게 느낀다는 형태로 이해)
    Gt=Rt+1+γRt+2+...G_t=R_{t+1}+\gamma R_{t+2}+...

  • state value function v(s)는 현재 state가 s일 경우 expected return 을 나타내는 함수이고 수식으로는 아래와 같이 표현된다
    v(s)=E[GtSt=s]v(s)=E[G_t |S_t=s]

  • state value function 에서 Bellman equation을 도출할 수 있다.

Bellman equation for MRP (Markov Reward Process)

  • 위의 value function 을 이용해 Bellman equation을 도출하는 과정은 아래와 같다.

v(s)=E[GtSt=s]=E[Rt+1+γRt+2+...St=s]=E[Rt+1+γGt+1St=s]=E[Rt+1+γE[Gt+1]St=s]=E[Rt+1+γv(St+1)St=s]=Rs+γsSPssv(s)\begin{aligned} v(s)&=E[G_t |S_t=s]\\ &= E[R_{t+1}+\gamma R_{t+2}+...|S_t=s]\\ &=E[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ &=E[R_{t+1}+\gamma E[G_{t+1}]|S_t=s] \\ &=E[R_{t+1}+\gamma v(S_{t+1})|S_t=s] \\ &=R_s + \gamma \sum_{s'\in S}P_{ss'}v(s') \end{aligned}
다이어그램으로 나타내면 아래와 같다.

  • value function은 역행렬로 연산가능 하지만 state 개수 n에 대해 O(n3)O(n^3) 의 time complexity를 갖기 때문에 향후 우리는 DP, Monte Carlo, Temporal-Difference 방법에 대해 배우게 된다.

Markov Decision Process

  • Markov Reward Process에 finite action set A가 추가되며 state transition probability matrix와 reward function 에 action A에 대한 조건이 추가된다.
    Pssa=P[St+1=sSt=s,At=a]Rsa=E[Rt+1St=s,At=a]P_{ss'}^a=P[S_{t+1}=s'|S_t=s,A_t=a]\\ R_s^a=E[R_{t_+1}|S_t=s,A_t=a]

  • policy는 아래와 같이 정의된다.
    π(as)=P[At=aSt=s]\pi(a|s)=P[A_t=a|S_t=s]
    이로부터 deterministic policy가 아닌 state s에서 어떤 action a를 취할 probability를 나타내는 stochastic한 방식을 택함을 알 수 있다

  • MDP에서 MRP로의 변환방법은 아래와 같다. 둘의 차이는 state transition probability matrix와 reward function에 있고 MDP에서 모든 action에 대해 합을 구한다면 action에 대해 고려하지 않은 MRP를 구할 수 있을 것이고 수식은 아래와 같다
    Pssπ=aAπ(as)PssaRsπ=aAπ(as)RsaP_{ss'}^\pi=\sum_{a\in A}\pi{(a|s)}P_{ss'}^a \\ R_s^\pi=\sum_{a\in A}\pi(a|s)R_s^a

  • value function은 이제 policy dependent하게 계산되며 식은 아래와 같다.
    vπ(s)=Eπ[GtSt=s]v_\pi(s)=E_{\pi}[G_t|S_t=s]
    새로운 개념인 action-value function이 도입되며 식은 아래와 같다.
    qπ(s,a)=Eπ[GtSt=s,At=a]q_\pi(s,a)=E_\pi[G_t|S_t=s,A_t=a]
    현재 state가 s이고 취하는 action이 a일 때 얻을 수 있는 return의 기대값을 의미한다.

Bellman equation for MDP (Markov Decision Process)

  • 직관적인 표현식은 각각 다음과 같다.
    vπ(s)=aAπ(as)qπ(s,a)...(1)qπ(s,a)=Rsa+γsSPssavπ(s)...(2)v_\pi(s)=\sum_{a\in A}\pi(a|s)q_\pi(s,a) \quad ...(1)\\ q_\pi(s,a)=R_s^a+\gamma \sum_{s'\in S}P_{ss'}^av_\pi(s') \quad ...(2)


    수식 (1)은 모든 action에 대한 확률과 action시 reward를 곱한 값으로 다음 action에 대한 기대값으로 이해할 수 있다.
    수식 (2)는 현재 택한 action에 대한 reward RsaR_s^a와 action 으로 인해 전환된 다음 state s'에서 얻을 return 의 기대값을 더한 것으로 이해할 수 있다.

  • 이로부터 value function 은 value function으로만, state value function은 state value function 으로만 표현하면 아래와 같다.
    vπ(s)=aAπ(as)(Rsa+γsSPssavπ(s))qπ(s,a)=Rsa+γsSPssaaAπ(as)qπ(s,a)v_\pi(s)=\sum_{a\in A}\pi(a|s)(R_s^a+\gamma \sum_{s'\in S}P_{ss'}^av_\pi(s')) \\ q_\pi(s,a)=R_s^a+\gamma\sum_{s'\in S}P_{ss'}^a\sum_{a'\in A}\pi(a'|s')q_\pi(s',a')

optimal value function

  • optimal state-value function 과 optimal action-value function은 각각 모든 policy에 대해 최대 값을 갖는 함수를 나타낸다.
    v(s)=maxvπ(s)q(s,a)=maxqπ(s,a)v_*(s)=max\,v_\pi(s) \\ q_*(s,a)=max\,q_\pi(s,a)

optimal policy

  • 어떤 Markov Decision Process에 대해서도 πππ\pi_* \geq \pi \quad \forall \pi를 만족하는 optimal policy π\pi_*가 존재한다.
    그리고 이 policy는 optimal value function을 도출한다.

  • optimal policy를 찾는 법은 optimal action value function에서 모든 action 들 중 가장 값을 최대로 만드는 action을 찾고 stochastic action 표현에서 그 action 에 대해서만 확률 1을 갖도록 만들면 되기 때문에 아래와 같이 표현가능하다.
    π(as)={1ifa=argmaxaA  q(s,a)0otherwise\pi_*(a|s)=\begin{cases} 1 & \text if \quad a=argmax_{a \in A} \; q_*(s,a) \\ 0 & \text otherwise \end{cases}

Bellman optimality equation

  • optimal value function은 다음과 같이 표현될 수 있다.
    v(s)=max  q(s,a)v_*(s)=max\;q_*(s,a)
    q(s,a)=Rsa+γsSPssav(s)q_*(s,a)=R_s^a+\gamma \sum_{s'\in S}P_{ss'}^av_*(s') \\
    위 식을 각각 다시 자신만을 사용해서 나타내면 아래와 같다
    v(s)=max  (Rsa+γsSPssav(s))v_*(s)=max\; (R_s^a+\gamma \sum_{s'\in S}P_{ss'}^av_*(s'))
    q(s,a)=Rsa+γsSPssamax  q(s,a)q_*(s,a)=R_s^a+\gamma \sum_{s'\in S}P_{ss'}^amax\;q_*(s',a' )

  • Bellman Optimality Equation은 max 함수 때문에 non-linear 하므로 iterative 한 방식으로 접근해야 한다.

profile
0100101

0개의 댓글