[RL] 마르코프 결정 과정 (Markov decision processes, MDP)

 

강화학습을 적용하기 위해서는 MDP 문제로 정의하는 것이 필요하다고 했는데, 그래서 MDP가 뭔데?

Markov property을 기반으로 하는 확률 모델

1. Markov Process (MP, 마르코프 과정)

* Markov Chain : 2023.07.14 - [🤖 ai/deep learning] - 베이즈 정리(Bayes’ theorem) & 마르코프 모델(Markov Models)

시간에 따라 확률적으로 변화하는 시스템을 모델링. 미래 상태는 현재 상태에만 의존하고 과거 상태에는 영향을 받지 않는다.

S, P로 구성

• 상태 집합 (State space, S): 시스템이 가질 수 있는 모든 가능한 상태들의 집합
• 상태 전이 확률 행렬 (Transition probability matrix, P): 현재 상태에서 다음 상태로 전이될 확률을 나타내는 행렬. $P_{ss\prime }$

2. Markov Reward Process (MRP, 마르코프 보상 과정)

Markov Process (MP)에 보상 개념을 추가한 것. 각 상태 전이마다 특정 보상을 받는다.

S, P, R, γ로 구성

• MP의 구성 요소 (상태 집합, 상태 전이 확률 행렬)
• 보상 (Reward, R): 각 상태에서 받는 보상
• 할인율 (Discount Factor, γ): 미래 보상의 가치를 현재 가치로 환산하는 데 사용되는 값 (0~1 사이).

3. Markov Decision Process (MDP, 마르코프 결정 과정)

Markov Reward Process (MRP) 에 의사 결정 요소를 추가한 것. 에이전트는 각 상태에서 행동을 선택하고, 그 결과로 보상을 받으며 학습하게 된다.

S, P, R, γ, A 로 구성

• MRP 의 구성 요소 (상태 집합, 상태 전이 확률 행렬, 보상, 할인율)
  • 상태 전이 확률 : s에서 a를 했을 때 s'에 도달할 확률 ($P_{ss\prime }^a$)로 MP, MRP와 비교하여 형태가 바뀜
• 행동 집합 (Action space, A): 에이전트가 각 상태에서 선택할 수 있는 모든 가능한 행동들의 집합. 정책 π로 규정한다.
• 정책 (Policy, π): 각 상태에서 에이전트가 선택할 행동을 결정하는 함수

 

Markov Decision Process

markov decision process는 에이전트가 있을 수 있는 다양한 상태들, 그들이 취할 수 있는 다양한 행동들, 그리고 다른 행동에 반하여 어떤 한 행동을 취했을 때 보상이 무엇인지를 나타낼 수 있는 모델이다.

 

기존의 Markov Chain은 하나의 상태가 어떤 확률 분포에 따라 다른 상태로 이어지는, 상태 전이의 확률만을 고려했다. 그러나 이는 어떤 행동을 취할 것인지, 그리고 그 행동이 어떤 결과를 가져올지에 대한 결정은 포함하지 않는다.

MDP(Markov Decision Process)는 이런 Markov Chain을 확장하면서 의사 결정 과정을 포함시킨 것이다. 상태뿐만 아니라 그 상태에서 취할 수 있는 행동, 그리고 행동에 따른 보상을 모델링하면서 환경과 상호작용할 수 있게 된다.

MDP(Markov Decision Process)는 다음과 같은 네 가지 요소로 구성된다.

 

• 상태(state) 집합 $S=1,...,n$
• 행동(action) 집합 $Actions(S)$
• 전이(transition) 모델 $P(s^{\prime }|s,a):=Prob(s_{t+1}=s^{\prime }|s_t=s,a_t=a)$
• 보상(reward) 함수 $R(s,a,s^{\prime })$

 

MDP에서의 강화학습의 목표는 에이전트가 기대 누적 보상(expected cumulative reward)을 최대화하는 최적의 정책(Policy)을 찾는 것이다.

기대 누적 보상이란, 특정 시점에서 시작하여 특정 정책을 따라 에이전트가 받을 수 있는 예상 보상의 합 (미래의 보상들의 합의 기댓값)을 말한다.

여기서 감가율(discount factor) γ이 주어졌을 때, t 시점에서 행동을 취했을 때의 기대 누적 보상은 다음과 같이 정의된다.

* 감가율(Discount Factor) : 미래의 보상에 대한 현재 가치를 결정하는 역할 (0과 1 사이의 값), $\gamma$가 0에 가까우면 당장의 보상만 고려하고, $\gamma$가 1에 가까우면 장기적인 보상도 고려한다.

 

$$E[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{R}_t]$$

 

기대 누적 보상(expected cumulative reward)을 최대화하기 위해서는 에이전트가 어떤 행동을 취할지 결정하는 규칙이 필요하다. 이를 Policy(정책)라고 한다.

Policy π는 주어진 상태에 대한 행동의 확률 분포로 표현된다.

 

$$\pi (a|s)=P[A_t=a|S_t=s]$$

 

Policy에 따라 행동을 선택하면, 기대 누적 보상(expected cumulative reward)도 달라지며, 이를 정책 가치 함수(Policy Value Function)라고 한다.

 

가치함수(Value Function)는 상태에 대한 기대 누적 보상의 합을 나타내는 함수라고 볼 수 있다.

(특정 상태의 "가치". 해당 상태에 도달했을 때 앞으로 얼마나 많은 보상을 얻을 수 있을지에 대한 기댓값)

즉, 특정 policy π를 따를 때 상태 s의 가치를 나타낸다.

 

$$V^{\pi }(s)=E_{\pi }[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{R}_t|S_t=s]$$

 

가치함수(Value Function)를 최대 가치 함수(maximum value function)로 나타내면 다음과 같고,

 

$$V^{\ast }(s)=\underset{a\in A}{max}{V}^{\pi }(s)=\underset{a\in A}{max}{E}_{\pi }[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{R}_t|S_t=s]$$

 

( $V^{\ast }(s)=\underset{a\in A}{max}{V}^{\pi }(s)=\underset{a\in A}{max}{Q}^{\ast }(s,a)$ 
최적 정책 π 는 각 상태에서 최적의 행동을 선택하는 정책.
따라서 상태 s에서 정책 π 를 따랐을 때 얻을 수 있는 최대 가치 $V^{\ast }(s)$는
결국 상태 s에서 최적의 행동을 선택했을 때의 가치 $Q^{\ast }(s,a)$와 같다는 것을 의미한다. )

 

여기서 $V^{\ast }(s)$는 상태 $s$의 최대 가치를 나타낸다.

 

가치 함수는 현재 정책이 얼마나 좋은지를 평가하고, 더 나은 정책을 찾을 수 있도록 도와주는 역할을 한다.

 

하지만, 가치함수(Value Function)는 상태에 대한 가치는 나타내지만, 행동에 대한 가치는 나타내지 않는다.

 

행동-가치 함수(action value function, Q-function) 행동에 대한 가치를 나타내는 함수로, 상태 s에서 행동 a를 취한 후 policy π를 따를 때의 기대 누적 보상을 나타낸다.

(특정 상태에서 특정 행동을 했을 때의 "가치". 해당 상태에서 해당 행동을 선택했을 때 앞으로 얼마나 많은 보상을 얻을 수 있을지에 대한 기댓값)

$$Q^{\pi }(s,a)=E_{\pi }[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{R}_t|S_0=s,A_0=a]$$

 

가치함수와 마찬가지로 행동-가치 함수(Q-function)를 최대 행동-가치 함수(maximum Q-function)로 나타내면 다음과 같다.

 

$$Q^{\ast }(s)=\underset{a\in A}{max}{Q}^{\pi }(s,a)$$

 

행동-가치 함수는 각 상태에서 어떤 행동을 선택해야 할지 알려준다.

 

즉, 가치 함수는 각 상태에서의 기대 보상을 나타내므로 정책 평가에 유용하고, 행동-가치 함수는 각 상태에서 어떤 행동을 해야 할지 알려주므로 정책 선택에 유용하다.

 

 

 

가치함수(Value Function)와 행동-가치 함수(Q-function)를 Bellman Equation(벨만 방정식)으로 재귀적으로 표현할 수 있는데, 이는 다음과 같다.

(왜? Bellman Equation으로 바꾸는가? 이렇게 하면 미래 보상(expected future reward)을 현재 보상(immediate reward)과 연결할 수 있다.

2024.06.25 - [🤖 ai/reinforcement learning] - [RL] MDP - Bellman equation)

 

$$V^{\ast }(s)=\underset{a\in A}{max}E[R_t+\gamma V^{\ast }(s_{t+1})|S_t=s]=\underset{a\in A}{max}(R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}^{\ast }(s^{\prime }))$$

$$Q^{\ast }(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}^{\ast }(s^{\prime })=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a\underset{a^{\prime }\in A}{max}{Q}^{\ast }(s^{\prime },a^{\prime })$$

 

$R_s^a$ : 상태 $s$에서 행동 $a$를 취할 때의 즉시 보상(immediate reward)

$\sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}^{\ast }(s^{\prime })$ : 다음 상태의 최적 가치(optimal value of next state)