All Posts

3장 그리드월드와 다이내믹 프로그래밍

Summary

1. 다이나믹 프로그래밍 - MDP를 풀기 위한 방법 (큰 일을 작게 쪼개서 수행하자)
2. 정책 이터레이션
   • 정책 평가
   • 정책 발전
3. 가치 이터레이션

• 전체적으로 다이나믹 프로그래밍의 정책 이터레이션과 가치 이터레이션 문제를 풀어나감 + 코드 설명

• 그리드월드는 다이내믹 프로그래밍의 도식화한 예시

다이나밍 프로그래밍

여기서 프로그래밍은 프로세스가 단계별로 나뉘어져 계획하는 것을 의미하고, 작은 문제가 중첩된 큰 문제일 경우 작은 문제로 쪼개서 푸는 방식.

정책 이터레이션

• 순차적 행동 결정 문제는 MDP를 통해 수학적으로 정의
• 문제의 목표는 에이전트의 보상의 합을 maximize 하는 것

정책은 에이전트가 모든 상태에서 어떻게 행동할지에 대한 정보이고 가장 높은 보상을 얻는 정책을 찾는것이 목표이다. 하지만 컴퓨터가 시작하는 정책은 무작위 정책(Random)이고, 이러한 정책을 정책 평가(Policy Evaluation)과 정책 발전(Policy Improvement)를 무한히 반복하여 최적 정책에 수렴할 수 있도록 하는 것이다. -벨만의 기대방정식을 활용함

• 정책 평가(가치 함수를 활용) - (코드 : Policyiteration 클래스의 poilcy_evaluation)

다이내믹 프로그래밍에서 에이전트는 정보가 없기 떄문에 랜덤 정책에서 시작하게 된다. 따라서 스텝을 밟아가면서 반복을 여러번 하였을때 정책에 대한 올바른 가치 함수를 찾을 수 있게 된다.(아래 수식에서 정책이 k iteration으로 바뀌게된 이유) $v_{k+1}(s) = \sum_{a \in A} \pi(a|s)(R_{s}^a + \gamma \sum_{s' \in S} P_{ss'}^{a} v_{k}(s'))$ 정책 평가의 순서는 다음과 같다. (책의 내용 참조)

1. k 번째 가치함수 행렬에서 현재 상태 s로 갈 수 있는 다음 상태 s’에 저장돼 있는 가치함수 $v_{k}(s’)$ 을 불러온다.
2. $v_{k}(s’)$ 에 감가율 $\gamma$ 를 곱하고 그 상태로 가는 행동에 대한 보상 $R_{s}^{a}$ 를 합한다. - $R_{s}^{a} + \gamma v_{k}(s’)$

3. 정책을 곱한다. - $\pi(a

   s)(R_{s}^{a} + \gamma v_{k}(s’))$

4. 모든 가능한 행동에 대해서 다 구하고 합한다. - $\sum_{a \in A}\pi(a

   s)(R_{s}^{a} + \gamma v_{k}(s’))$

5. 합한 값을 k+1번째 가치함수 행렬 s자리에 저장한다.
6. $s \in S$ 에 대해 반복한다.

• 정책 발전(일종의 weight 업데이트) - (코드 : PolicyIteration 클래스의 poilcy_improvement)) 탐욕 정책 발전(Greedy Policy Improvement)를 활용하여 새로운 정책 업데이트 한다.(상태 중 가장 높은 value function을 가진 상태로 가는 것)

​ 즉, max 상태 값으로 가는 것이다!!

정책 평가와 정책 발전을 계속적으로 반복하여 가치 함수가 수렴하는 순간을 정책으로 한다

가치 이터레이션

행동가치함수(q함수)를 최대화 하여 벨만의 최적방정식(optimal)을 찾아가는 것이다.

정책이터레이션과 같이 정책 평가, 정책 발전이 이루워지는 것이 아니라 가치이터레이션은 마지막에 구해진 큐함수 값을 보고 max값에 따라 정책을 정한다. 즉, 확률적인 정책으로 정책을 결정하는 정책이터레이션과 달리 가치 이터레이션은 벨만 큐함수의 max값(큐함수간 비교)을 바로 업데이트 한다. 벨만최적방정식과는 다르게 가치 이터레이션 역시 k iteration을 돌려 업데이트해간다.

Summary

• MDP(Markov Decision Process)에 대한 수식
  • 상태(State)
  • 행동(Action)
  • 보상 함수(Reward function)
  • 상태변환확률(State Transition Probability)
  • 감가율 (Discount Factor)
• 정책(Policy)
• 가치함수(Value Function)
  • 상태 가치함수 (State Value function)
  • 행동 가치함수 (Action Value function) - 큐함수
• 벨만 방정식
  • 벨만 기대방정식
  • 벨만 최적방정식

1. MDP(Markov Decision Process)

   순차적 행동 결정 문제를 풀 때 수학적으로 표현하는 방식.

   • 상태 (State)

     에이전트가 관찰 가능한 상태의 집합 S(Random Variable) , state는 action에 따라( Transition Probability) 다음 state로 변함.

     ex) $S_{t} = s$ : 시점 t에서 가능한 상태의 집합에서 특정한 상태 s

   • 행동 (Action)

     $S_{t}$에 할 수 있는 모든 행동의 집합 A(Random Variable)

     ex) $A_{t}=a$: 시점 t에서 가능한 상태의 집합에서 특정한 행동 a

   • 상태변환확률(State Transition Probability) - 환경의 모델

     t 시점 s 상태에서, t시점 s 상태에서 a 행동을 취했을때, t+1 시점에서 s’ 상태일 확률.

   $$P^{a}_{ss'} = P[S_{t+1}=s'|S_{t}=s, A_{t}=a]$$
   • 감가율(Discount Factor)

가까운 보상에 더 큰 가중치를 두기 위한 비율 $\gamma \in {[0,1]}$

ex) t시점에서 시간 2이 지났을때 $\gamma ^{2-1}$ 만큼 보상(Reward)에 곱하겠음.

• 보상 함수(Reward Function)

에이전트가 학습할 수 있는 유일한 정보. 환경으로 부터 시간 1(time step)이 지난 다음 받는 보상에 대한 기대값.

t 시점 s 상태에서, t 시점 a 행동을 행하였을 때, t+1시점의 보상의 기대값(Expectation). 결국 행동으로 인해 보상을 받는 것이다(결과 때문에 받는 것이 아님) $R^{s}_{a} = E[R_{t+1}|S_{t}=s, A_{t}=a]$

1. 정책(Policy)

   에이전트가 어떤 s(상태)에 도착하였을 어떤 a(행동)를 행해야할지 골라주는 것. 강화학습은 결국 최적의 정책을 목적으로 하고, MDP에서는 얻은 보상들의 합이(Reward)을 최대화하는 정책을 찾는다. $\pi(a|s) = P[A_{t}=a|S_{t}=s]$

2. 가치함수(Value Function)

   어떠한 상태에 있으면 앞으로 얼마의 보상을 받을 것인지에 대한 기대값을 나타내는 함수

   • 상태 가치 함수(State-value function) - v(s)

     t시점 s 상태일 때, t시점 확률변수 G(Return)에 대한 기대값. 쉽게 말해 s 상태의 가치이고, 에이전트는 다음으로 갈수 있는 상태들(집합 S에 있는 것들) 중 높은 가치를 선택하는 것.
     $v(s) = E[G_{t}|S_{t}=s]$

     • $G_{t}$ (Return) : t시점으로부터 감가된 보상들의 총합
     $$G_{t} = R_{t+1}+\gamma R_{t+2}+ \gamma ^{2}R_{t+3}+.... = \sum_{k=0}^\infty \gamma ^kR_{t+k+1}$$ $$G_{t} = R_{t+1}+\gamma G_{t+1}$$

     t시점 G는 t+1시점의 보상 R 과 감가율읠 적용한 t+1 시점의 G의 합이됨.

   • 행동 가치 함수(Action-value function) - 큐함수

     어떤 s상태에서 어떤 a행동을 할 경우 받을 G(return)값에 대한 기대값을 나타내는 함수. 어떤 행동을 하면 얼마나 좋을까를 나타내줌. $q_{\pi}(s,a) = E_{\pi}[G_{t}|S_{t} = s, A_{t}=a]$

     $$q_{\pi}(s,a) = E_{\pi}[R_{t+1}+\gamma q_{\pi}(S_{t+1},A_{t+1})|S_{t} = s, A_{t}=a]$$

3. 벨만방정식(Bellman Equation)

   특정 정책에서 현재(t 시점) 상태의 가치 함수와 다음 상태(t+1시점)의 보상과 다음 상태(t+1시점) 가치함수의 합을 식을 나타낸 것

   • 벨만 기대 방정식

   상태 가치 함수

   $$v_{\pi}(s) =E_{\pi}[R_{t+1}+ \gamma v_{\pi}(S_{t+1}) | S_{t}=s]$$ $$v_{\pi}(s) = \sum_{a \in A} \pi(a|s)(R_{s}^a + \gamma \sum_{s' \in S} P_{ss'}^{a} v_{\pi}(s')) -계산 가능한 벨만 방정식$$

   행동 가치 함수(큐함수)

   $$q_{\pi}(s,a) =E_{\pi}[R_{t+1}+ \gamma q_{\pi}(S_{t+1},A_{t+1}) | S_{t}=s, A_{t}=a]$$ $$q_{\pi}(s,a) = \sum_{a \in A} \pi(a|s)(R_{s}^a + \gamma \sum_{s' \in S} P_{ss'}^{a} \sum_{a' \in A} \pi(a'|s') q_{\pi}(s',a')) -계산 가능한 벨만 방정식$$

   여기서 s’, a’ 은 다음 시점의 상태와 행동을 의미함.

   정책 $\pi (a

   s)$ 는 어떠한 행동을 할 확률을 의미함.

   • 벨만 최적 방정식

     최적 상태 가치 함수

     $$v_{*}(s) =\max_{\pi} v_{\pi}(s)$$

     최적 행동 가치 함수(큐함수)

     $$q_{*}(s,a) =\max_{\pi} q_{\pi}(s,a)$$

You’ll find this post in your _posts directory. Go ahead and edit it and re-build the site to see your changes. You can rebuild the site in many different ways, but the most common way is to run jekyll serve, which launches a web server and auto-regenerates your site when a file is updated.