Lecture 2: Markov Decision Processes

1. Markov Processes

Markov Processes는 State와 Probability로 정의되며, time-step 마다 확률에 따라 다음 state로 넘어가며, 이를 반복한다. 이때, State의 집합을 $\mathcal{S}$이라 하고, 확률의 행렬을 $\mathcal{P}{ss’}$(State transition matrix) 라고 한다. 즉, Markov Process는 $<\mathcal{S}, \mathcal{P}{ss’}>$의 tuple 형태로 정의할 수 있다. 이를 Markov Chain이라 하기도 한다.

1.1. State Transition Probability

상태 전이 확률 마르코프 상태 s가 그 다음 상태인 s’로 전이되는 확률을 의미한다.

\[\mathcal{P}_{ss'} = \mathbb{P} \ [S_{t+1} = s' \mid S_t = s]\]

1.2. State Transition Matrix

상태 전이 행렬은 모든 상태 s에서 모든 그 다음 상태 s’로의 전이 확률을 정의한다.

\[\mathcal{P} = \begin{bmatrix} \mathcal{P}_{11} & \mathcal{P}_{12} & \cdots & \mathcal{P}_{1n} \\ \mathcal{P}_{21} & \mathcal{P}_{22} & \cdots & \mathcal{P}_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ \mathcal{P}_{n1} & \mathcal{P}_{n2} & \cdots& \mathcal{P}_{nn} \\ \end{bmatrix}\]

$\mathcal{P}{11}$은 1번 state에서 다음 state가 1번일 확률이며, $\mathcal{P}{21}$은 2번 state에서 1번 state로 전이될 확률이다. 즉, $\mathcal{P}_{nn}$은 n번 state에서 n번 state로 전이될 확률을 의미한다.

각 행(row)의 확률을 모두 더하면 1이 된다. 각 행마다 그 행의 수를 제외하고 나머지를 선택할 확률을 나열했기 때문이다. 예를 들어, 2번째 행에서 $\mathcal{P}{21}$부터 $\mathcal{P}{2n}$까지 나열되어 있다. 2번 state가 1번, 2번, 3번, … , n번 state로 전이될 확률을 나열한 것이다. 2번 state 기준에서 이동은 한 번만 되므로 각 행의 확률을 모두 더하면 1이 되야만 한다.

1.3. Episodes Example

시작 state에서 시작해서 마지막 state까지 도착한 걸 하나의 에피소드라고 한다. 시작 state는 임의로 설정할 수 있다. 그러나 학습을 시작하면 시작 state를 고정해야 한다.

아래 그림에서 보면, “C1 C2 C3 Pass Sleep”, “C1 FB FB C1 C2 Sleep” 등과 같이 나열된 것들이 각각 하나의 Episode를 나타낸 것이다. ‘Class1’ state에서 ‘Class2’로, ‘Class2’ state에서 ‘Class3’ state로 전이되는 것을 나타낸 것이다. 에피소트를 얻는 과정을 샘플링이라 칭한다. (ex. Sampling을 한다, Sampling을 얻는다.) 위 state를 State Transition Matrix로 나타내면 다음과 같다.

State Transition Matrix

2. Markov Reward Processes

Markov Reward Process는 값을 갖는 마프코프 프로세스이며, $ <\mathcal{S}, \mathcal{P}{ss’}, \mathcal{R}, \mathcal{\gamma}> $로 정의할 수 있다. $\mathcal{S}, \mathcal{P}{ss’}$는 Markov Process와 동일하다. 그저, Markov Process에서 $\mathcal{R}, \mathcal{\gamma}$만 추가 됐을 뿐이다.

2.1. Reward function

state를 입력 받으면 해당 state에 맞는 reward를 반환하는 함수이다. 어떤 state에 도달하면 얼만큼의 reward를 주는 것이다. 아래 함수를 보면 t번째 state를 입력하면 t+1번째 reward를 반환한다.

\[\mathcal{R}_s = \mathbb{E} \ [R_{t+1} \ | \ S_t = s]\]

Exmaple: Markov Reward Process

MRP에서는 State에만 reward를 부여한다. 어떤 행동을 해서 어떤 state로 가는게 아니라 확률에만 의존하여 다음 state로 행한다. 때문에 action에는 reward를 부여하지 않는다.

2.2. Return

return은 한 에피소드에서 받는 reward의 총량이다. 강화 학습은 Return을 최대화하는게 목적이다. 흔히 reward를 최대화하는게 아닌가 하지만 둘은 다른 개념이다. 혼동하지 않도록 주의하자. reward를 더할 때 그냥 더하지 않고 $\gamma$를 곱해서 감가상각하여 더해준다.

$$

$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + … = \sum\limits_{k=0}^\infin \gamma^kR_{t+k+1}$

$$

2.3. Discount factor

Return에서 $\gamma$를 곱해줌으로써 장기적인 보상이 아니라 즉각적인 보상을 중요시한다.

• $\gamma$가 0에 가까우면 “근시적”으로 평가한다.
• $\gamma$가 1에 가까우면 “원시적”으로 평가한다.

$$

$\gamma \in [0, 1]$

$$

왜 Discount factor를 곱해줘야 할까??

다양한 이유가 있지만 대표적인 이유는 수학적으로 편리하기 때문이다. Discount factor를 활용함으로써 수렴성이 증명된다. 수렴해야 다른 값과 비교하여 큰지 작은지 판단할 수 있다.

• 수학적으로 편리하다.
• 주기적인 마르코프 프로세스에서 무한한 수익을 방지한다.
• 미래에 대한 불확실성이 완전히 표현되지 않을 수 있다.
• 보상이 재정적인 경우, 즉각적인 보상은 지연된 보상보다 더 많은 이자를 얻을 수 있습니다.
• 동물/인간 행동이 즉각적인 보상을 선호하는 것으로 나타났기 때문이다.

문제에 따라 Discount factor가 더 필요할 수도 있고 덜 필요할 수도 있다.

2.4. Value Function

MRP에서 Value Function은 return의 기댓값이다. 더 정확히 이야기하자면, 어떤 state에서 어떤 policy를 따라 샘플링 했을 때 얻는 return이다.

$$

$V(s) = \mathbb{E} \ [ \ G_t \mid S_t = s]$

$$

2.5. 벨만 방정식(Bellman Equatoin)

벨만 방정식은 다음 state의 보상과 다음 state의 Value Function에 Discount factor를 곱한 값으로 나타낸다.

$$

$V(s) = \mathbb{E} \ [ \ G_t \mid S_t = s] \ \
= \mathbb{E} \ [ \ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + … \mid S_t = s] \ \
= \mathbb{E} \ [ \ R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + … \ ) \mid S_t = s] \ \
= \mathbb{E} \ [ \ R_{t+1} + \gamma G_{t+1} \mid S_t = s] \ \
= \mathbb{E} \ [ \ R_{t+1} + \gamma V(S_{t+1}) \mid S_t = s]$

$$

Expectation을 제거하기 위해선 해당 state를 가는 확률을 곱해줘야 한다.

s에서 s’로 가는 상황에서 벨만 방정식을 구할 떄 자세하게 구어체로 설명하면 다음과 같다.

“벨만 방정식은 항이 2개이다. 첫 번째 항은 s에서 s’로 갈 때 얻는 reward($\mathcal{R_s}$)이고, 두 번째 항은 여러 인수의 곱이다. 우선, 가고자 하는 state s’의 가치함수인 $V(s’)$에다가 s에서 s’로 가는 확률인 $\mathcal{P}_{ss’}$을 곱하고 마지막에 Discount factor를 곱해준다.”

Example: Bellman Equation for Student MRP

벨만 방정식의 예시를 보면 시그마($\sum$)가 붙는 이유를 알 수 있다. 결론부터 말하면, s’로 가는 s가 하나가 아니기 때문이다. 예시의 오른쪽 위를 보면 빨간색 State(이하 s’)에서의 벨방 방정식을 계산한 결과이다. 우선 s’의 reward는 -2이고, 2개의 state에서 s’를 향할 수 있다. 하나는 0.8의 확률로, 다른 하나는 0.4의 확률로 s’를 향하고 있다. 그렇기에 s’의 벨만 방정식을 계산하기 위해선 확률과 value function을 곱하고 모두 더해줘야 한다.

예시는 reward, state transition probability, value function, bellman equation이 모두 정해진 상태에서 벨만 방정식이 성립하는지 확인하는 과정이었다. 어떻게 각 값을 계산했는지 아직 묻지 말자. 차근차근 강의를 듣다 보면 알 수 있다.

2.5.1. 벨만 방정식의 매트릭스 형태 (Bellman Equation in Matrix Form)

벨만 방정식은 행렬을 사용하여 간결하게 표현할 수 있다.

$$

$V = \mathcal{R} + \gamma \mathcal{P}V$

$$

\[\begin{bmatrix} V(1) \\ \\ \vdots \\ \\ V(n) \end{bmatrix} = \begin{bmatrix} \mathcal{R_1} \\ \\ \vdots \\ \\ \mathcal{R_n} \end{bmatrix} + \gamma \begin{bmatrix} \mathcal{P}_{11} & \mathcal{P}_{12} & \cdots & \mathcal{P}_{1n} \\ \mathcal{P}_{21} & \mathcal{P}_{22} & \cdots & \mathcal{P}_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ \mathcal{P}_{n1} & \mathcal{P}_{n2} & \cdots& \mathcal{P}_{nn} \\ \end{bmatrix} \begin{bmatrix} V(1) \\ \\ \vdots \\ \\ V(n) \end{bmatrix}\]

각 행은 해당 인덱스의 state를 의미한다. 예를 들어, 1번째 state의 벨만 방정식은 1번째 행이다. 정확한 식은 아래와 같다.

$$

$V(1) = \mathcal{R_1} + \gamma \begin{bmatrix} \mathcal{\ P_11 \ \cdots \ \mathcal{P_1n} \ } \end{bmatrix} V(1)$

마찬가지로 n번째 state의 벨만 방정식은 n번째 행이다.

벨만 방정식은 선형 방정식이다. 따라서 아래와 같은 전개가 가능하다.

때문에 우리는 $\gamma$만 알고 있으면 value function을 바로 계산할 수 있다. $\mathcal{P}$과 $\mathcal{R}$은 Markov Reward Process를 정의하려면 무조건 필요하다. 즉, 우리가 이미 알고 있는 값이란 뜻이다. 이것이 없으면 MRP를 정의할 수 없기 때문이다.

벨만 방정식의 계산 복잡도는 O($n^3$)의 복잡도를 가진다. 그래서 작은 MRP에서만 가능하다. 작다는 것의 state의 수(n)가 적음을 의미한다. 큰 MRP에서 벨만 방정식을 계산하는 방법도 있다. 그 예시는 아래와 같다.

• Dynamic programming
• Monte-Carlo evaluation
• Temporal-Difference learning

3. Markov Decision Processes

Markov Decision Processes(이하 MDP)는 MRP에서 action이 추가된 것이다. 그래서 action을 추가한 $<\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \mathcal{\gamma}>$으로 정의한다.

• $\mathcal{S}$: state의 집합

• $\mathcal{A}$: action의 집합

• $\mathcal{P}$: state transition probability matrix

$\mathcal{P}{ss’}^\mathrm{a} = \mathbb{P} \ [S{t+1} = s’ \mid S_t = s, A_t = \mathrm{a}]$

• $\mathcal{R}$: reward function

$\mathcal{R}{s}^\mathrm{a} = \mathbb{E} \ [R{t+1} \mid S_t = s, A_t = \mathrm{a}]$

• $\gamma$: discount factor

$\gamma \in [0, 1]$

MDP는 강화 학습을 위한 환경을 형식적으로 기술하는 방법이다. 또한, MDP는 환경을 완전히 관찰할 수 있는 경우이다. 즉, Fully Observable Environments 이다.

Example: Student MDP

빨간색 글씨는 action을 나타낸 것이다. MDP는 MRP와 달리 action을 했을 때 reward를 받는다. MRP는 state마다 rewerd를 받기 떄문에 어느 state에 도달했는지에 따라 reward가 달라지지만 MDP는 어떤 action을 하냐에 따라 reward가 달라진다.

MDP에서 action을 했을 떄 다음 state로 가는 것은 확률에 의해 결정된다. “Pub” action을 했을 때 0.2, 0.4, 0.4의 확률로 state가 나뉜다. 또한, state에서 action의 가짓수가 하나라면 1.0의 확률을 갖고 있는 것이다.

3.1. Policy

Policy는 주어진 state에서 action를 할 확률을 의미한다. 즉, policy는 state에서 action의 확률 분포이다.

$\pi(a \mid s) = \mathbb{P} \ [A_{t} = \mathrm{a} \mid S_t = s \ ]$

policy는 에이전트의 동작을 완전히 정의한다. MDP에서 policy는 현재 state에만 의존한다. history없이 현재 state만 있으면 policy를 계산할 수 있기 때문이다.

$A_t \sim \pi(\cdot \mid S_t), \forall t > 0$

$\forall$(for all)은 ‘모든’이라는 뜻의 전칭 기호이다. 즉, $\forall t > 0$ 은 모든 t는 0 보다 크다라는 것을 의미한다.

따라서, MDP에서 정책은 시간에 독립적이다. 에이전트가 특정 state에 도달했을 때 어떤 행동을 취할 것인지를 결정하는 기준이 항상 동일하다는 것을 의미한다. 이러한 policy는 일정한 확률로 다른 상태로 이동하거나 다른 보상을 받는 상황에서도 적용될 수 있으며, 이를 통해 에이전트는 일관된 행동 패턴을 유지할 수 있다.

[심오한 내용]

해당 내용은 넘어가도 되는 영역이라 한다. 나중에 봤을 때 이해가 된다면 좋을 것 같다.

1. MDP $\mathcal{M} = < \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma >$와 policy가 주어지고, policy가 고정된 상태라고 가정하자. 이때, state sequence $\mathcal{S}_1, \mathcal{S}_2, …$ 은 그냥 Markov process $< \mathcal{S}, \mathcal{P}^\pi >$라고 봐도 무방하다. policy가 고정됐다는 뜻은 어던 state에서 어떤 action을 선택할지에 대한 확률이 고정됐다는 뜻이다. 또한 어떤 action을 선택하고 그 action에 의해 state s에서 state s’로 갈 확률($\mathcal{P}$)도 주어져있으므로 state s에서 state s’로 가는 확률도 고정되어 있다고 볼 수 있다. 정확한 수식은 아래와 같다.

$\mathcal{P}{s,s’}^\pi = \sum\limits{\mathrm{a \in \mathcal{A}}} \pi(a \mid s) \mathcal{P}_{ss’}^\mathrm{a}$

1. MDP에서 state와 reward의 sequence $\mathcal{S}_1, \mathcal{R}_2, \mathcal{S}_2, …$는 Markov reward process $< \mathcal{S}, \mathcal{P}^\pi, \mathcal{R}^\pi, \gamma >$라고 봐도 무방하다. MDP에서 reward는 action을 취했을 때 받는다. 윗 문단에서 어떤 action을 선택할지, 그 확률이 고정됐다고 이야기하였다. 즉, state s에서 state s’로 갈 때 어떤 reward를 받게 되는지 알 수 있다는 뜻이다. 수식으로 생각하면 아래와 같다.

$\mathcal{R}s^\pi = \sum\limits{\mathrm{a \in \mathcal{A}}} \pi(a \mid s) \mathcal{R}_s^\mathrm{a}$

3.2. Value Function

action의 유무에 따라 2개의 value function으로 나뉜다.

3.2.1. state-value function

MDP에서 value functin은 어떤 state에서 policy $\pi$를 따라서 샘플링했을 때 return을 의미한다.

$V_\pi (s) = \mathbb{E}_\pi \ [\ G_t \mid S_t = s \ ]$

3.2.2. action-value function

state action-value function이라고도 하는데 어떤 state에서 어떤 action을 취하고 $\pi$를 따라 에피소드를 샘플링 했을 때의 return을 의미한다. 또한, q 함수라고도 한다. Q-learning, DQN 등등 q 함수를 학습 시키는 강화 학습 알고리즘이다.

$q_\pi (s, a) = \mathbb{E}_\pi \ [\ G_t \mid S_t = s, A_t = \mathrm{a} \ ]$

Example: State-Value Function for Student MDP

3.3. 벨만 기대 방정식 (Bellman Expectation Equation)

3.3.1. state-value function

$V_\pi (s)= \mathbb{E}\pi \ [ \ R{t+1} + \gamma V_\pi(S_{t+1}) \mid S_t = s \ ]$

3.3.2. action-value function

$q_\pi (s, \mathrm{a})= \mathbb{E}\pi \ [ \ R{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) \mid S_t = s, A_t = \mathrm{a} \ ]$

3.3.3. state-value function ↔ action-value function

흰 원은 state를, 검은 원은 action을 의미한다.

v를 q로 표현

$V_\pi (s) = \sum\limits_{\mathrm{a} \in \mathcal{A}} \pi(\mathrm{a} \mid s) q_\pi(s, \mathrm{a})$

q를 v로 표현

$q_\pi(s, \mathrm{a}) = \mathcal{R}s^\mathrm{a} + \gamma \sum\limits{s’ \in \mathcal{S}} \mathcal{P}{ss’}^\mathrm{a} V\pi (s’)$

“v를 q로 표현”한 것에 “q를 v로 표현”한 것 대입

$V_\pi (s) = \sum\limits_{\mathrm{a} \in \mathcal{A}} \pi(\mathrm{a} \mid s)
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (\ \mathcal{R}s^\mathrm{a} + \gamma \sum\limits{s’ \in \mathcal{S}} \mathcal{P}{ss’}^\mathrm{a} V\pi (s’) \ )$

“q를 v로 표현”한 것에 “v를 q로 표현”한 것 대입

$q_\pi(s, \mathrm{a}) = \mathcal{R}s^\mathrm{a} + \gamma \sum\limits{s’ \in \mathcal{S}} \mathcal{P}{ss’}^\mathrm{a}
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \sum\limits{\mathrm{a’} \in \mathcal{A}} \pi(\mathrm{a’} \mid s’) q_\pi(s’, \mathrm{a’})$

Example: Bellman Expectation Equation in Student MDP

3.3.4. Bellman Expectation Equation (Matrix Form)

벨만 기대 방정식은 MRP를 사용하여 간결하게 표현할 수 있으며, MRP에서 벨만 방정식 전개한 것처럼 하면 $V_\pi$를 새롭게 정의할 수 있다.

$V_\pi = \mathcal{R}^\pi + \gamma \mathcal{P}^\pi V_\pi$

$V_\pi = (I - \gamma \mathcal{P}^\pi)^{-1} \mathcal{R}^{\pi}$

3.4. Optimal Value Function

3.4.1. optimal state-value function

policy의 수는 거의 무한이라 봐도 무방하다. policy가 무한하다면 state-value function도 무한할 것이다. 그 중 가장 큰 state-value function을 optimal state-value function이라 한다. 가장 크다는 것은 다른 의미로 가장 좋다고도 볼 수 있다. 즉, optimal state-value functin은 state-value function 중 가장 좋은 것을 말한다.

$V_*(s) = \max\limits_{\pi} V_\pi (s)$

3.4.2. optimal action-value function

거의 무한에 가까운 action-value function 중 가장 좋은 것을 의미한다.

$q_*(s, \mathrm{a}) = \max\limits_{\pi} q_\pi (s, \mathrm{a})$

• Optimal Value Function은 MDP에서 가능한 최상의 성능을 나타낸다.
• MDP에서 Optimal Value Function을 찾았을 때 MDP를 “풀었다”라고 한다.

Example: Optimal Value Function for Student MDP

Example: Optimal Action-Value Function for Student MDP

3.5. Optimal Policy

3.5.1. partial ordering

Optimal Policy를 하기 전에 두 policy를 비교하는 방법을 정의해야 한다. 두 policy 중 좋은 것을 판단하는 방식은 아래와 같다.

$\pi \geq \pi’$ if $V_\pi (s) \geq V_{\pi’} (s), \forall s$

→ 모든 state에서 $V_\pi (s)$가 $V_{\pi_*}(s)$ 보다 크다면, $\pi$는 $\pi’$보다 크다.

모든 MDP는 다음 정리를 만족한다. 똑똑한 석박사 행님들께서 증명한 정리이기 때문에 받아들이자.

• 다른 모든 정책보다 낫거나 같은 최적의 정책 $\pi_$가 존재한다, $\pi_ \geq \pi, \forall \pi$

• 모든 최적의 정책이 최적의 가치 함수를 달성한다. $V_{\pi_} (s) = V_ (s)$

  → $\pi_$를 따라갔을 때 $V_{\pi_}$는 $V_* (s)$와 같다.

• 모든 최적의 정책이 최적의 행동 가치 함수를 달성한다. $q_{\pi_} (s, \mathrm{a}) = q_ (s, \mathrm{a})$

  → $\pi_$를 따라갔을 때 $q_{\pi_}$는 $q_* (s)$와 같다.

optimal policy는 하나가 아니라 여러 개일 수도 있다.

3.5.2. Optimal Policy 찾기

$\pi_* (\mathrm{a} \mid s) = \begin{cases} \ \ 1 \ \ \ \ \ \mathrm{if} \ \ \mathrm{a} = \argmax\limits_{\mathrm{a} \in \mathcal{A}} \ q_* (\mathrm{s}, \mathrm{a})
\ \ 0 \ \ \ \ \ \mathrm{otherwise} \end{cases}$

Optimal policy는 다음과 같은 특성을 갖고 있다.

• 모든 MDP 에서 항상 deterministic optimal policy가 존재한다.
• 만약 우리가 $q_* (s, \mathrm{a})$를 안다면, 우리는 즉시 optimal policy를 가지고 있다. 즉, $q_* (s, \mathrm{a})$를 알면, $\pi_* (a \mid s)$ 하나는 알게 된다.

deterministic(결정론적인)은 자신이 하는 행동의 미래를 정확히 알고 있는 것을 말한다. deterministic optimal policy는 어떤 state에서 action이 하나로만 선택할 때를 의미한다. 예를 들어, 가위바위보 게임을 할 때 deterministic optimal policy는 ‘가위’, ‘바위’, ‘보’ 중에 하나만 계속해서 내는 것이다. 33.3%의 확률이 가장 높은 확률이기 때문이다. 만약, 상대방이 50% 확률로 ‘바위’만 낸다면, 50%의 확률로 ‘가위’만 내는 것이 optimal policy이고, deterministic optimal policy이다. 이러한 deterministic optimal policy가 모든 MDP에서 무조건 존재한다는 것이 신비롭다.

deterministic의 반대되는 의미로 stochastic(확률적인)이 있다. 내가 선택한 행동이 의도한 대로 될지 안 될지 모르지만 확률적으로 추정할 수 있음을 의미한다. policy는 근본적으로 stochastic이다. 그러나 optimal policy는 deterministic 하게 존재한다.

Example: Optimal Policy for Student MDP

위 예시에서 빨간색 화살표가 optimal policy를 의미한다.

3.5.2. Bellman Optimality Equation

$V_(s) = \max\limits_{\mathrm{a}} q_(\mathrm{s}, \mathrm{a})$

$q_$를 최대화 하는 a를 선택한 $q_$가 $V_(s)$이다. 즉, $q_$의 최댓값이 $V_*(s)$이다.

$q_(\mathrm{s}, \mathrm{a}) = \mathcal{R}_\mathrm{s}^\mathrm{a} + \gamma \sum\limits_{\mathrm{s’} \in \mathcal{S}} \mathcal{P}_{\mathrm{s}\mathrm{s’}}^\mathrm{a} V_ (\mathrm{s’})$

$V_(s) = \max\limits_{\mathrm{a}} \mathcal{R}_\mathrm{s}^\mathrm{a} + \gamma \sum\limits_{\mathrm{s’} \in \mathcal{S}} \mathcal{P}_{\mathrm{s}\mathrm{s’}}^\mathrm{a} V_ (\mathrm{s’})$

$q_(\mathrm{s}, \mathrm{a}) = \mathcal{R}_\mathrm{s}^\mathrm{a} + \gamma \sum\limits_{\mathrm{s’} \in \mathcal{S}} \mathcal{P}_{\mathrm{s}\mathrm{s’}}^\mathrm{a} \max\limits_{\mathrm{a’}} q_(\mathrm{s’}, \mathrm{a’})$

Example: Bellman Optimality Equation in Student MDP

max는 그저 가장 큰 값을 선택하는 것이기에 상황에 따라 반환값이 달라질 수 있다. 그래서 각 수들의 관계를 선형으로 표현할 수 없다.

선형 방정식이 아니기 때문에 그저 전개해서 풀 수 없다(No closed form solution). 마찬가지로 역행렬 등을 구할 수 없다. 이것이 Bellman Expectation Equation와 Bellman Optimality Equation의 차이점이다.

Bellman Optimality Equation을 풀기 위해선 아래와 같은 방법이 있을 수 있다.

• Value Iteration
• Policy Iteration
• Q-Learning
• Sarsa

4. Reference

• 강의 영상 - https://www.youtube.com/watch?v=NMesGSXr8H4&list=PLpRS2w0xWHTcTZyyX8LMmtbcMXpd3s4TU&index=2
• 강의 자료 - https://www.davidsilver.uk/wp-content/uploads/2020/03/MDP.pdf