- Markov Decision Process는 RL(강화학습)을 위한 environment(환경)을 공식적으로 설명 - 거의 모든 RL문제는 MDP로 형식화할 수 있다.
=> environmnet가 완전히 fully observable(관찰 가능)할때. 즉, 현재 상태가 과정을 완전히 설명
Markov Property(속성)
"현재가 주어지면 미래는 과거와 독립적이다."
상태 St가 Markov임을 의미하려면 다음 조건을 만족해야 함.
- State는 과거로부터 얻는 모든 관련 정보를 포함 - 현재 State를 알면, 과거의 정보는 무시할 수 있다. => 즉, State는 미래 예측에 필요한 충분한 통계량이다.
State Transition Matrix(상태 전이 행렬)
State Transition Probability
Markov 상태 S와 다음 상태 S'에 대해
State Transition Matrix
State Transition Matrix P는 모든 상태 S에서 다음 상태 S'로의 transition probabilities을 정의함
=> 행렬의 각 행의 합은 "1"
Markov Process(과정)
- 기억이 없는 random 확률 과정이다. => 즉, Markov Property를 가진 상태들의 연속적인 열 S1,S2,...이다.
Markov Process(Markoc Chain)은 다음과 같은 튜플 <S,P>로 구성됨 - 유한한 State 집합 S - State transition probability matrix P
EX) 학생이 여러 활동을 전이하는 Markov Chain.
=> 첫번째 행 C1 상태에서의 전이 확률 두번째 행 C2 상태에서의 전이 확률 ... => 각 행의 합은 "1"
Markov Reward Process(보상 과정)
값을 가진 Markov chain
MRP는 다음과 같은 튜플<S,P,R,Γ>로 구성 - S: 유한한 집합 상태 - P: state transition propability martix - R: 보상 함수
- Γ: 할인 요인
EX) Student MRP
Return(반환)
시간 단계 t부터의 총 할인된 보상
- Γ(할인률): 미래 보상의 현재 가치
: K+1시간 단계 후 보상 R을 받을 때의 가치
- discount factor(할인률)이 높을수록 agent가 먼 미래의 보상에 더 많은 관심을 가짐. 1. if Γ=0: agent는 myopic(근시안적), 즉각적인 보상만 중시 2. if Γ=1: agnet는 far-sighted(원시안적), 즉 미래 보상을 현재 보상과 동일하게 중시.
Why Discount?
대부분의 Markov reward(and decision)은 discount된다. WHY? 1. Discount 하는것이 수학적으로 편리하다. 2. 순환하는 Markov Process에서 무한 반환을 방지한다. 3. 미래에 대한 불확실성이 완전히 표현되지 않을 수 있다. 4. 보상이 재정적인 경우, 즉각적인 보상은 지연된 보상보다 가치가 크다. 5. 동물/인간의 행동은 즉각적인 보상을 선호하는 경향이 있다. 6. 때때로 undiscounted Markov reward process를 사용할 수 있다. (종료 상태가 있는 에피소드 과제)
Value Function(가치 함수)
상태 S의 장기적인 가치를 제공
MRP에서 가치 함수 v(S)는 상태 S에서 시작하는 기대 반환
EX) Student MRP returns
- Γ=1/2일 때 반환 G1:
(1)
- Γ=0일 때, 즉각적인 보상만 고려 => 각 상태의 보상 값은 단기적인 보상만 반영하므로, PASS상태에서만 높은 보상을 받으며, 나머지 상태에서는 각각의 상태에서 바로 받는 보상이 상태 가치로 지정
(2)
- Γ=0.9일 때, 미래 보상도 상당 부분 고려 => 각 상태에서 장기적인 보상을 반영한 상태 가치가 표현, PASS상태는 여전히 높은 가치, 다른 상태에서도 가치가 다소 높아짐
(3)
- Γ=1일 때, 모든 미래 보상이 현재 보상과 동일한 가치를 가짐 => 장기적 관점에서의 상태 가치가 각 상태에 반영, YouTube같은 상태는 반복적으로 저평가되는 경향을 보임, PASS상태로 가는 경로가 상대적으로 더 높은 가치를 가짐.
EX) Bellman Equation for MRPs
value function은 2가지로 분류 가능 1. 즉각적인 보상 Rt+1 2. 후속 상태의 discounted value Γv(St+1)
value function v(s):
- s: 현재 상태/ r: 즉각적인 보상/ s': 다음 상태
v(C3): 상태 C3에서 시작할 때의 기대 가치가 계산된 예시 => 각 상태의 가치 함수는 현재 상태에서 즉각적인 보상과 다음 상태의 할인된 기대 가치의 합으로 구성
Bellman Equation in Matrix Form
v: 각 상태에 대해 하나의 값을 가지는 열 벡터
Solving the Bellman Equation
- Bellman 방정식은 linear 방적식 - 선형 대수학의 표준 기법으로 해결 가능
- n개의 상태에 대한 계산 복잡도:
- 상태 수가 많아질수록 직접적인 계산이 어려워짐. - 큰 MRP의 경우 다음과 같은 반복적인 방법들이 사용: Dynamin programming, Monte-Carlo evaluation, Temporal-difference learning
Markov Decision Process(결정 과정)
MDP는 결정이 포함된 Markov reward process, 모든 state가 Markov 상태인 환경을 나타냄.
MDP는 다음과 같은 튜플<S,A,P,R,Γ>로 구성 - S: 유한한 상태 집합 - A: 유한한 행동 집합 - P: state transition probalility matrix
- R: reward function
- Γ: discount factor
EX) Student MDP
Policy
policy π는 특정 state에서 가능한 행동에 대한 확률 분포
- At: t시점에서 취해지는 행동 - St: 해당 시점의 상태
- Policy는 Agent의 행동 방식을 완전히 정의하며, 과거가 아닌 현재 상태에만 의존 - MDP에서 Policy는 정적(stationary) - 즉, 모든 시간 t>0에 대해 동일하게 적용
- 주어진 MDP <S,A,P,R,Γ>와 policy π가 있을때
- state sequence S1,S2,...은 Markov process를 형성 - state and reward sequence S1,R2,S2.R3,..은 Markov reward proceass를 형성
Value Function(가치 함수)
State-Value Function
State S에서 시작하여 Policy π를 따른 경우의 기대 반환
Action-Value Function
State S에서 행동a를 선택하고 이후 Policy π를 따른 경우의 기대 반환
EX) State-Value Fuction for Student MDP
Bellman Expectation Equation
- State-Value Function은 즉각적인 보상과 후속 상태의 discount된 가치로 분해 가능 - Action-Value Function도 비슷하게 분해 가능
State-Value Function
Action-Value Function
EX) Student MDP
Bellman Expection Equation (Matrix Form)
- Bellman 방정식은 유도된 MRP를 사용하여 행렬 형태로 간결하게 표현 가능
- 직접 해
Optimal Value Function
Optimal state-value function(최적 상태-가치 함수)
모든 policies에 대해 최대 값이 되는 함수로 정의
Optimal action-value function(최적 행동-가치 함수)
모든 policies에 대해 최대 값이 되는 함수로 정의
- Optimal Value Function은 MDP에서 가능한 최고의 성능을 나타냄. - MDP는 Optimal state-value function와 Optimal action-value function을 알게 되면 해결되었다고 본다.
EX) Studnet MDP
- 각 상태에서 가능한 최적의 가치(가치 함수)를 나타낸다. - v*(s)는 각 상태에서 최적의 행동을 선택한 결과 얻을 수 있는 최대의 기대 보상
- 상태뿐만 아니라, 상태에서 선택한 행동에 따라 가치가 어떻게 달라지는지를 보여준다. - q*(s, a)는 상태 s에서 행동 a를 선택할 때의 최적 기대 보상
Optimal Policy
모든 MDP에서 다음이 성립 1. 모든 policy보다 더 나은 Optimal plocy가 존재
2. 모든 Optimal policy는 Optimal value function을 만족
3. 모든 Optimal policy는 Optimal action-value function을 만족
Finding an Optimal Policy
Optimal policy는 Optimal action-value function을 최대화하는 행동을 선택하여 찾을 수 있다. - 모든 MDP에는 deterministic optimal policy가 항상 존재합니다. - 만약 q∗(s,a)를 알고 있다면 최적 정책을 즉시 얻을 수 있다.
EX) Student MDP
- 최적 정책이 각 상태에서 최적의 행동을 선택하여 장기적인 가치를 극대화하는 방법
Optimal State-Value Function
Optimal Action-Value Function
EX) Student MDP
Solving the Bellman Optimal Equation
- Bellman Optimality Equation은 비선형 방적식 - 반복적 방법(iterative methods)을 사용하여 방정식을 해결 Value iteration, Policy iteration, Q-learning, Sarsa ....
