Search

AI/ Markov Decision Process(MDP)

Markov Decision Process(MDP)

Reinforcement Learning(RL)은 에이전트가 환경과 순차적으로 상호작용하면서 학습하는 패러다임이고, 여기서 에이전트의 목표는 할인된 누적 보상을 최대화 하기 위한 행동 선택 정책을 최적화하는 것이다. Markov Decision Process(MDP)는 Model-based 방법의 한 종류로 Markov Decision Process를 기반으로 하는 강화 학습 방법이다(Model-based의 다른 종류에는 Nonlinear Dynamics 형태가 있고, Model-Free 방법은 Gradient Free(off policy, on policy)와 Gradient-based 방법이 존재한다)

Basics

Markov Decision Process는 강화학습의 수학적 모델로, 에이전트가 환경과 상호작용하면서 최적의 정책을 찾는 문제를 정의하는 방식으로 다음과 같은 형식으로 정의 된다.
M=(S,A,P,R,γ)\mathcal{M} = (S, A, P, R, \gamma)
여기서 SS는 State Space로 환경이 가질 수 있는 모든 상태의 집합을 나타내며, AA는 Action Space로 에이전트가 수행할 수 있는 모든 행동의 집합을 나타내며, P(s′∣s,a)P(s'|s, a)는 State Transition Probability로 현재 상태 ss에서 행동 aa를 수행할 때, 다음 상태 s′s'로 전이될 확률을 나타내며, R(s,a)R(s, a)는 Reward Function으로 상태 ss에서 행동 aa를 수행할 때 주어지는 보상을 나타내며, γ\gamma는 미래 보상에 대한 할인율(discount factor)를 나타낸다.
강화학습은 MDP를 기반으로 최적의 정책 π(a∣s)\pi(a|s)를 학습하여 보상을 최적화하는 것이 목표인 방법이라 할 수 있다.

Trajectory

강화학습에서 에이전트가 환경과 상호작용하며 생기는 궤적(trajectory)는 MDP에서의 연속적인 전이 과정을 나타낸다. 정책 π\pi 하에 길이 TT의 궤적 τ\boldsymbol{\tau}를 생성하는 확률은 아래처럼 작성할 수 있다.
p(τ)=p0(s0)∏t=0T−1π(at∣st)pT(st+1∣st,at)pR(rt∣st,at,st+1)p(\boldsymbol{\tau}) = p_0(s_0)\prod_{t=0}^{T-1} \pi(a_t|s_t)p_T(s_{t+1}|s_t,a_t)p_R(r_t|s_t,a_t,s_{t+1})
여기서
•
p0(s0)p_0(s_0)는 MDP 상태 집합에서의 초기 상태를 나타내고,
•
π(at∣st)\pi(a_t|s_t)는 에이전트가 행동을 선택하는 정책(policy)이고,
•
pT(st+1∣st,at)p_T(s_{t+1}|s_t, a_t)는 tt 시점의 상태와 행동을 조건으로 t+1t+1 시점에 대한 상태로 전이하는 상태 전이 확률이고,
•
pR(rt∣st,at,st+1)p_R(r_t|s_t, a_t, s_{t+1})은 tt 시점의 상태와 행동(과 optional로 t+1t+1시점의 상태 포함)를 조건으로 tt 시점의 보상을 나타내는 보상 확률을 의미한다.

Episode and returns

에지전트가 환경과 영원히 상호작용하는 경우 continuing task라 부른다. 반면 어떠한 종료 조건이 존재하여(목표를 달성하거나 실패하는 등) 환경과의 상호작용이 종료될 수 있는 경우 episodic task라 한다. ss가 absorbing state라면 다음 상태는 항상 ss이고 reward는 00이다.
시간 tt 이후 앞으로 얻을 것으로 기대하는 보상의 합을 GtG_t이라 정의한다. 여기서 각 보상은 할인율 γ∈[0,1]\gamma \in [0, 1]을 적용하여 계산한다.
Gt≜rt+γrt+1+γ2rt+2+...+γT−t−1rT−1=∑k=0T−t−1γkrt+k=∑j=tT−1γj−trj\begin{aligned} G_t &\triangleq r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + ... + \gamma^{T-t-1}r_{T-1} \\ &= \sum_{k=0}^{T-t-1} \gamma^k r_{t+k} = \sum_{j=t}^{T-1} \gamma^{j-t}r_j \end{aligned}
GtG_t는 때때로 reward-to-go라고 부른다. 시간 TT에서 종료되는 에피소딕 작업의 경우 t≥Tt \ge T에 대해 Gt=0G_t = 0라고 정의할 수 있고 G0G_0은 에피소드 시작(t=0t=0)에서부터 종료 시점까지 기대되는 보상의 총합이 나타낸다.
GtG_t은 다음과 같은 재귀 관계를 만족한다.
Gt=rt+γ(rt+1+γrt+2+...)=rt+γGt+1G_t = r_t + \gamma(r_{t+1} + \gamma r_{t+2} + ...) = r_t +\gamma G_{t+1}

State Value Function

상태 ss에서 시작하고 이후에는 정책 π\pi를 따라 행동을 선택할 때 받을 기대 보상의 총합을 나타내는 함수 Vπ(s)V_\pi(s)를 state-value 또는 value 함수라고 부른다.
Vπ(s)≜Eπ[G0∣s0=s]=Eπ[∑t=0∞γtrt∣s0=s]V_\pi(s) \triangleq \mathbb{E}_\pi[G_0|s_0=s] = \mathbb{E}_\pi \left[\sum_{t=0}^\infty \gamma^t r_t|s_0 = s \right]

Action Value (Q) Function

state-value와 유사하지만 상태 ss에 대한 행동 aa를 지정하고, 이후에는 정책 π\pi를 따라 행동을 선택할 때 받을 기대 보상의 총합을 나타내는 함수 Qπ(s,a)Q_\pi(s, a)를 action-value 함수 또는 Q-함수라고 한다.
Qπ(s,a)≜Eπ[G0∣s0=s,a0=a]=Eπ[∑t=0∞γtrt∣s0=s,a0=a]Q_\pi(s,a) \triangleq \mathbb{E}_\pi [G_0|s_0 = s,a_0=a] = \mathbb{E}_\pi \left[ \sum_{t=0}^\infty \gamma^t r_t|s_0=s,a_0=a \right]

Advantage Function

상태 ss에서 정책 π\pi를 따를 때의 기대 보상(즉 Vπ(s)V_\pi(s))을 baseline으로 보고, 상태 ss에서 행동 aa를 선택할 때의 기대보상(즉 Qπ(s,a)Q_\pi(s, a))이 baseline에 비해 얼마나 좋은지 여부를 따질 수 있는데, 이를 계산하는 함수를 Advantage Function이라 하고 아래처럼 정의된다.
Aπ(s,a)≜Qπ(s,a)−Vπ(s)A_\pi(s,a) \triangleq Q_\pi(s,a) - V_\pi(s)
현재 상태 ss에 대한 행동 aa이 baseline 보다 나을 경우 값이 커지고 그렇지 못한 경우 Advantage는 음수가 될 수 있다.

Optimal Value Functions

π∗\pi_*가 모든 상태 s∈Ss \in \mathcal{S}와 모든 정책 π\pi에 대해 Vπ∗≥VπV_{\pi_*} \ge V_\pi를 만족하는 정책이라 하면 이것은 optimal policy가 된다. 동일한 MDP에 대한 여러 최적 정책이 있을 수 있지만 정의상 해당 가치 함수가 동일해야며 각각 V∗V_*와 Q∗Q_*로 표기된다. 이때 V∗V_*을 optimal state-value 함수라하고 Q∗Q_*를 optimal action-value 함수라고 한다. 모든 유한 MDP는 적어도 1개의 결정론적 최적 정책을 가져야 한다.
최적 가치 함수는 근본적으로 Bellman’s optimality 방정식으로 나타낼 수 있다(여기서 Bellman 방정식은 현재 상태의 최적 가치가 미래 상태의 최적 가치와 관계를 갖는 재귀적 형태의 식을 말한다).
V∗(s)=max⁡aR(s,a)+γEpT(s′∣s,a)[V∗(s′)]Q∗(s,a)=R(s,a)+γEpT(s′∣s,a)[max⁡a′Q∗(s′,a′)]\begin{aligned} V_*(s) &= \max_a R(s,a) + \gamma \mathbb{E}_{p_T(s'|s,a)}[V_*(s')] \\ Q_*(s,a) &= R(s,a) + \gamma \mathbb{E}_{p_T(s'|s,a)}\left[ \max_{a'} Q_*(s',a') \right] \end{aligned}
이상적인 최적이 정의가 되므로 현재 가치 함수와 이상적인 최적 사이의 차이를 정의할 수 있다. 이것을 Bellman Error(또는 Bellman Residual) 이라 하며, 아래와 같이 구할 수 있다.
BE=V(s)−V∗(s)=V(s)−[max⁡aR(s,a)+γEpT(s′∣s,a)[V∗(s′)]]BE=Q(s,a)−Q∗(s,a)=Q(s,a)−[R(s,a)+γEpT(s′∣s,a)[max⁡a′Q∗(s′,a′)]]\begin{aligned} \text{BE} &= V(s) - V_*(s) = V(s) -\left[ \max_a R(s,a) + \gamma \mathbb{E}_{p_T(s'|s,a)}[V_*(s')]\right] \\ \text{BE} &= Q(s, a) - Q_*(s,a) = Q(s,a) -\left[ R(s,a) + \gamma \mathbb{E}_{p_T(s'|s,a)}\left[ \max_{a'} Q_*(s',a') \right]\right]\end{aligned}
물론 최적의 값 V∗V_*와 Q∗Q_*를 알 수 없 없기 때문에, 다음과 같이 V∗V_*와 Q∗Q_*에 대한 근사치 V^,Q^\hat{V}, \hat{Q}를 정의하고
V^(s)=max⁡a[R(s,a)+γV(s′)]Q^(s,a)=R(s,a)+γmax⁡a′Q(s′,a′)\begin{aligned} \hat{V}(s) &= \max_a [R(s,a) + \gamma V(s')] \\ \hat{Q}(s,a) &= R(s,a) + \gamma \max_{a'} Q(s',a') \end{aligned}
이 근사치와의 차이를 통해 Bellman Error를 추정한다.
BE≈V(s)−V^(s)=V(s)−[max⁡a[R(s,a)+γV(s′)]]BE≈Q(s,a)−Q^(s,a)=Q(s,a)−[R(s,a)+γmax⁡a′Q(s′,a′)]\begin{aligned} \text{BE} &\approx V(s) - \hat{V}(s) = V(s) - \left[ \max_a [R(s,a) + \gamma V(s')]\right] \\ \text{BE} &\approx Q(s, a) - \hat{Q}(s,a) = Q(s,a) - \left[ R(s,a) + \gamma \max_{a'} Q(s',a')\right] \end{aligned}
그리고 이 근사치와의 차이값(Bellman Error)를 줄이는 방식으로 모델을 학습하고, 이 차이값이 00이 되면 모델이 최적에 도달했다고 한다.

Optimal Policies

Q∗(s,a)Q_*(s,a)를 최대화 하는 행동 aa는 상태 ss에 대한 최적 정책 π∗(s)\pi_*(s)에 해당 되므로 Q∗(s,a)Q_*(s,a)를 이용하여 아래와 같이 최적 정책 π∗(s)\pi_*(s)을 구할 수 있다.
π∗(s)=arg max⁡aQ∗(s,a)\pi_*(s) = \argmax_a Q_*(s,a)
한편 주어진 상태 ss를 최대화한 값이 최적 상태 가치 V∗(s)V_*(s)가 되므로 Q∗(s,a)Q_*(s,a)를 이용하여 아래와 같이 최적 상태 가치 V∗(s)V_*(s)를 구할 수 있다.
V∗(s)=max⁡aQ∗(s,a)V_*(s) = \max_a Q_*(s, a)
위 식들을 정리하면 최적 정책 π∗(s)\pi_*(s)에 대해 다음과 같이 식을 정리할 수 있다.
π∗(s)=arg max⁡aQ∗(s,a)=arg max⁡a[R(s,a)+γEpT(s′∣s,a)[V∗(s′)]]\begin{aligned} \pi_*(s) &= \argmax_a Q_*(s,a) \\ &= \argmax_a [R(s,a) + \gamma \mathbb{E}_{p_T(s'|s,a)}[V_*(s')]] \end{aligned}
즉 행동 가치 함수만 이용해서 최적 정책을 구할 수 있고(첫 번째), 행동 가치 함수 없이 보상을 결합한 상태 가치 함수를 이용하여 최적 정책을 구할 수도 있다(두 번째). 따라서 최적 정책을 구할 때 행동 가치 함수를 이용하거나 보상과 결합된 상태 가치 함수를 이용한 방법을 사용할 수 있다.
V∗,Q∗,π∗V_*, Q_*, \pi_*를 푸는 문제를 policy optimization이라 하며, 주어진 정책 π\pi에 대한 VπV_\pi나 QπQ_\pi를 푸는 것을 policy evaluation이라 한다

참고

Made with