[CS234]Lecture 2. Markov Process, MRPs, MDPs, Evaluation and Control
이번 강의에서는 Markov Process와 MRP,MDP, MDP에서의 Control 과 Evaluation에 대해서 알아본다
Markov Assumption
들어가기에 앞서서 마르코프 가정을 한번 확인해보자.
State $s_{t}$ is Markov if and only if
$$ p ( s_{t+1} | s_t , a_t ) = p ( s_{t+1} | h_t , a_t ) $$
즉 미래 상태는 과거의 상태들에 독립적이고, 현재 상태에만 의존하게 된다. 따라서 미래의 상태를 결정하기 위해서 과거의 상태를 고려하지 않는다.
Markov Process
Markov Process는 주어진 상태 s에서 다음 상태 s로의 상태 전이가 이루어지는 과정을 말한다.
Sequence of Random States with Markov Property
👉 특징
No Reward, No Actions, Memoryless property
Memoryless Property: 미래상태를 결정하는데에 현재상태를 제외한 history를 알 필요가 없음
Transition Probability:
S: (finite)set of States
P: trainsition model that specifies $ p ( s_{t+1} | s_t , a_t ) = p ( s_{t+1} | h_t , a_t ) $
만약 states가 finite number(N)갯수만큼 존재하는 경우에 대해서, P를 다음과 같은 matrix로 나타낼 수 있다.
이 matrix를 Markov Chain Trainsition Matrix라고 한다.
쉬운 이해를 위해 강의의 예시를 참고하자.
개별 state는 총 7개 이고, 다음 state로의 전이 확률을 간단하게 표현하고 있다.
이 경우 P는 아래와 같이 작성할 수 있을 것이다
Markov Reward Process (MRP)
위의 Markov Process에서는 Reward과 Action이 포함되지 않은 개념이었다. MRP는 Markov Chain에 Reward가 추가된 것으로 생각할 수 있다.
MRP는 다음을 통해 정의 한다.
S: (finite) sets of states
P: trainsition model that specifies $ p ( s_{t+1} | s_t , a_t ) = p ( s_{t+1} | h_t , a_t ) $
R: Reward function $ R ( s_{t} =s) = \mathbb{E} [r_t|s_t=s] $ 만약 가능한 state가 유한개(N)이라면 R은 벡터로 표현가능하다.
Discount Factor $\gamma \in [0,1]$ 미래의 Reward를 얼마만큼 반영할지를 결정한다.
여전히 여기에 Action에 대한 정보는 존재하지 않음을 기억하자.
Horizon & Return Function
Horizon: Number of time steps in each episode.
즉, 한번에 얼마만큼의 future를 확인할 것인지에 대한 값이다.
Horizon은 infinite일수도 있고, finite값일 수도 있다. 만약 horizon이 finite인 경우에는 MRP를 finite MRP라고 부른다.
Return: Discounted Sum of Rewards from timestep t to horizon H
시간 t로부터 시작해서 Horizon개의 Reward를 Discount Factor $\gamma$를 적용해서 더한 값을 말한다.
수식을 보면 더 이해가 쉽다
$$G_t = r_t+\gamma r_{t+1}+\gamma^2 r_{t+2}+...+\gamma^{H-1} r_{t+H-1}$$
State Value Function
Value: Expected Return from starting in state s
t일때의 state 가 s일때, Return의 기대값을 V(s)라고 한다.
$$V(s) = \mathbb{E}[G_t|s_t=s]$$
Value는 이후에 policy를 평가하고, optimal policy를 결정하는데에 도움을 준다.
Computing Value of MRP
가치함수를 계산하는 방법을 알아보자.
MRP에서 value function은 다음을 만족한다
방법1. Bellman Equation
Value Fucntion은 벨만 방정식을 이용해서 재귀적으로 표현이 가능하다.
앞서서 finite state (N)인 경우에 대해서 P와 R이 행렬로 표현됨을 알았다. 따라서 이를 Matrix Form으로 계산할 수 있다.
초록색 부분이 우리가 알고있는 정보이다.
우리가 알고 싶은 것은 V이므로 식을 정리하면 다음과 같다.
이 과정을 통해서 Value값을 계산할 수 있다.
방법 2. DP
위에서는 재귀적으로 구했으니, DP로 순차적으로 구해볼 수 있다.
Markov Decision Process (MDP)
MDP의 경우 MRP에 Action이 추가된 것으로 생각할 수 있다.
따라서 Reward를 계산할 때 Action또한 고려하게 된다.
Policy
policy는 agent가 특정 state에서 어떻게 action할지에 대한 규칙을 말한다.
이 Policy는 Deterministic하게 정해져있을 수도 있고, 확률을 통해서 stochastic할 수도 있다.
Policy는 다음처럼 표기한다
만약 Stochastic Policy의 경우 위처럼 확률로 표현하게 되고, Deterministic Policy의 경우 s에 대한 action이 정해져있기 때문에 다음처럼 표현한다.
Bellman Backup
앞서서 MDP는 MRP+Policy 라는것을 배웠다.
따라서 Policy가 결정된다면, MDP를 MRP로 축소하여 생각할 수 있다.
Policy : $\pi$ 라고 하면 MRP로 다음과 같이 표현할 수 있다.
따라서 MRP에서 Value를 계산했던 것과 같은 로직을 통해 특정 Policy $\pi$일때의 Value를 계산할 수 있고, 이를 통해 정책을 평가할 수 있게 한다.
MDP Control
우리가 원하는것은 MDP의 정보 그 자체도 있겠지만, Optimal 한 Policy가 무엇인지를 아는 것이다.
Optimal Policy가 뭐냐고 한다면 아래처럼 말할 수 있을 것이다.
Policy Search
그래서 이 Optimal Policy를 어떻게 구할 수 있을까?
Opt Policy를 찾는 방법 중 하나가 Policy Iteration이다.
Policy Iteration
Policy Iteration 의 과정은 다음과 같다.
그래서 Policy를 어떻게 Improve시킬까?
이를 위해서 Q (State-Action Value) 라는 새로운 Value Function을 도입한다.
즉, State-Action Value Q는기존 우리가 알아봤던 Value와 달리 state s에서의 action a가 policy와 관계없이 모든 Action에 대해서 계산된다는 것이다.
따라서 $Q^{\pi}(s,a)$는 $\pi(s)$를 따른 경우의 Value를 포함하게 된다.
이 말은 Q가 max가 되는 경우의 policy가 기존의 policy와 동일하거나 더 나은 policy가 된다.
그럼 위의 Policy Iteration의 과정을 다시 살펴보면
While문의 의미는 policy가 optimal하여 Q를 통해서 더 나은 policy가 존재하지 않는 경우에 반복문을 종료한다는 의미이다.
당연한 말이지만, 기존의 policy의 V(s)값 보다 maxQ값이 더 큰 경우, 기존의 policy를 버리고, 얻은 새로운 policy를 쓴다.
