Markov Decision Process (MDP) & Bellman Equation

강화학습에서 가장 중요한 것을 다시 짚어보면 다음과 같습니다. 

• Environment: Agent를 제외한 모든 것
• State: 환경 중에서도 우리에게 필요한 정보들
• Rewards: Agent가 판단을 내렸을 때 이에 대한 보상값(스칼라)
• Return: 리워드의 기댓값(최종적으로 받을 수 있는 보상의 기댓값)
• Agent
  • Policy
    • deterministic: 어떤 state에서는 어떤 action을 해라
    • stochastic: 이런 state에서는 이런 action을 할 확률이 얼마 
  • Value: 리턴의 기댓값
    • 이 상황이 얼마나 좋은지 나쁜지를 나타내는 값
  • Model: action을 했을 때 받을 수 있는 리워드에 대한 정의
    • 내가 이 행동을 하면 어디로 갈까? (어떻게 될까?)

 

Markov Property

현재의 나의 state는 이전 state에만 영향을 받는다

이렇게 하면 문제가 단순해 집니다

Markov Process : S, P

• A Markov process is a memoryless random process
• A Markov process is a stochastic process that has the Markov property, which means that the future state of the process depends only on the present state, and not on any past states

Markov process는 '문제를 모델링하기 위한 방법론'입니다. S는 state의 유한집합이고, P는 state transition matrix 혹은 state transition probability입니다. 

Example

예를 들어, 세상에 수원시와 용인시만 있다고 해 봅시다. 

수원에 살다가 용인으로 이사를 가는 사람도 있고, 용인에 살다가 수원으로 이사를 가는 사람도 있겠죠? 그냥 그대로 남는 사람도 있을 겁니다. 그래서 그걸 state transition이라고 하고 State transition matrix가 다음과 같다고 정의를 해 봅시다. 

2023년에 수원에는 1만명이 살고, 용인에는 1.2만명이 살고 있다고 했을 때 2024년에는 어떻게 될까요 ? 

10년후에는 어떻게 될까요 ?

이런 식으로 Markov 특성을 이용해서 state의 변화를 계산할 수 있다는 것입니다. 

Markov Reward Process : S, P, R, γ

Markov reward process는 Markov chain에 reward를 더한 것입니다. 

R은 state에 대한 Reward입니다. 그런데 '리워드를 언제 받는 것인가?'가 조금 헷갈릴 수 있습니다. 리워드는 떠날 때 받습니다. 그 state에서 action을 하면 그때 받는 것이 reward이고, 그렇기 때문에 reward는 timestamp가 +1 되어서 표기됩니다. 

그리고 gamma는 return 값을 계산할 때 나와 멀리 있는 애들의 reward값을 조금 discount하는 것에 관한 파라미터입니다. 

return Gt는 reward*discount factor의 합

γ가 0에 가까우면 '나한테 지금 닥친 것만 생각하겠어'라는 것이고, γ가 1에 가까우면 '멀리 보겠다'는 것입니다. 수학적으로는 discount factor가 있으면 수렴이 잘 된다는 것이 증명되어 있습니다. 또한 Cyclic markov process가 있을 때 무한대의 리턴이 나오는 것을 방지하는 역할도 있습니다. 

value function은 복습해 보면 내가 어떤 state일 때 앞으로 받을 보상의 기댓값입니다.

example : state-value function for Student MRP

이런 state와 state transition matrix가 정의되어 있을 때

State 1의 value는 다음과 같이 구할 수 있습니다.

Bellman Equation for MRPs

국민연금을 1년에 천 만원씩 받을 수 있다고 가정해봅시다. 그러면 65세인 사람의 국민연금의 밸류는 (1000만원 + 66세의 기댓값)과 같다는 것입니다. 

따라서 Value function은 두 가지 파트로 나눌 수 있습니다. 

• Immediate reward R_t+1
• Discounted value of successor state γv(S_t+1)

일단 하나 먹고, 그 다음 애의 기댓값을 쓰겠다는 겁니다. 
벨만 방정식은 선형적이기 때문에 다음과 같이 바로 풀 수가 있습니다. 

그런데, 여기서 문제는 역행렬을 구하는 것이 연산이 엄청 많다는 것입니다.

저렇게 구하기에는 state가 너무 많습니다. 이런 direct한 해결책을 쓸 수 없기 때문에 이후에 다룰 Dynamic programming(모델을 알 때 사용 가능), Monte-Carlo evaluaion, Temporal difference(모델을 몰라도 사용 가능) 등이 고안되었습니다. 

Markov Decision Process : S, P, A, R, γ

MDP는 MRP + decision입니다. 그리고 decision은 다른 말로 action이라고도 합니다.

A가 들어갔기 때문에 P는 이제 "State와 Action이 주어졌을 때 S'로 이동할 확률"입니다. 그리고 이때도 마찬가지로, 리워드는 '액션을 했을 때' 받게 됩니다. 

Policies

• A policy π is a distribution over actions in given states
• A policy fully defines the behavior of an agent

 

 

---

위 내용은 경희대학교 소프트웨어융합학과 황효석 교수님의 2023년 <강화학습> 수업 내용을 요약한 것입니다.