[RL] Markov Decision Process

Markov Process

$\mathbf{Definition.}$ Markov State

State $S_t$가 다음과 같은 조건을 만족할 경우, $S_t$가 Markov property를 만족한다고 한다. 또는 $S_t$를 Markov state라고 부른다.

$$
\begin{align*}
  P[S_{t+1} | S_t] = P[S_{t+1} | S_1, \cdots, S_t]
\end{align*}
$$

 

즉, 어떤 마르코프 상태 $S_t = s$와 다음 상태 $S_{t+1} = s^\prime$라면, 다음과 같은 확률 값이 정의될 수 있다.

$$
\begin{align*}
  \mathcal{P}_{ss^\prime} = P[S_{t+1} = s^\prime | S_t = s]
\end{align*}
$$

 

이 확률은 상태 전이 확률, state transition probability라고 한다. 만약 상태 공간이 유한하다면, 모든 state $s$에서 다음 상태 $s^\prime$으로 가는 상태 전이 확률을 모아 다음과 같은 행렬을 구성할 수 있다.

$$
\mathcal{P}= \left[\begin{array}{ccc}
\mathcal{P}_{11} & \ldots & \mathcal{P}_{1 n} \\
\vdots & & \\
\mathcal{P}_{n 1} & \ldots & \mathcal{P}_{n n}
\end{array}\right]
$$

 

각 행 element의 합은 $1$인 것을 확인할 수 있다. 이와 같은 행렬을 상태 전이 행렬, state transition matrix라고 한다.

$\mathbf{Definition.}$ Markov Process 

Markov process, 또는 Markov Chain는 튜플 $\left\langle \mathcal{S}, \mathcal{P} \right\rangle$의 형태로 표현될 수 있는 random process로, 각 원소들은 다음 조건을 만족한다:

 

1. $\mathcal{S}$는 finite state space
2. $\mathcal{P}$는 transition probability matrix
   
   $$
   \begin{align*}
     \mathcal{P}_{ss^\prime} = P[S_{t+1} = s^\prime | S_t = s]
   \end{align*}
   $$

 

Markov process는 노드로 대응되는 state와 간선으로 대응되는 상태 전이 확률 값으로 이루어진 그래프 형태로 주로 나타낸다. 

 

$\mathbf{Fig\ 1.}$ Graphical representation of Markov chain

 

이 경우 state transition matrix $\mathcal{P}$는 다음과 같다. 

 

위의 확률 과정은 sleep state에 도달하면 종료되는 것을 볼 수 있다. 이처럼 특정 state에 도달하면 process가 종료될 경우, 해당 state를 terminal state로 명칭한다. 또한 그래프에서 주로 원 대신 사각형의 노드로 이 state를 표현한다. 강화학습 task도 이 terminal state 존재 유무에 따라 2가지 종류로 구분된다. 

 

Episodic Tasks: terminal state가 존재
Continuous Tasks: terminal state가 존재하지 않음 

 

 

따라서 위의 예시는 episodic task로 분류된다. 각 state의 시작부터 마지막 종료 시점의 state까지의 시퀀스를 episode로 정의한다. 예를 들면, Class 1 - Class 2 - Class 3 - Pass - Sleep 가 하나의 예시다.

 

강화학습 알고리즘의 디자인은 terminal state 유무에 따라서도 영향을 받는다. 따라서 위의 정의는 반드시 기억해두어야 한다.

---

Markov Reward Process

앞서 설명한 Markov process을 강화학습 문제에서 다루기 위해선, 반드시 agent에게 주어지는 reward가 필요하다. 우리는 이를 위해  Markov process를 Markov reward process로 확장한다. 

$\mathbf{Definition.}$ Markov Reward Process. 
A Markov Reward Process는 $$\left\langle \mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma \right\rangle$$의 튜플로 나타내며, 각 element는 다음과 같은 특성을 갖는다: 

1. $\mathcal{S}$는 finite state space
2. $\mathcal{P}$는 transition probability matrix
   
   $$
   \begin{align*}
     \mathcal{P}_{ss^\prime} = P[S_{t+1} = s^\prime | S_t = s]
   \end{align*}
   $$
3. $\mathcal{R}$는 reward 함수로, 다음과 같이 정의된다. 
   
   $$
   \begin{align*}
     \mathcal{R}_{s} = \mathbb{E} [R_{t+1} | S_t = s]
   \end{align*}
   $$
4. $\gamma \in [0, 1]$는 discount factor로 불린다.

 

Return and Value Function

RL 에이전트의 궁극적인 목표는 cumulative reward, 즉 episode동안 받는 reward를 최대화하는 것을 목적으로 한다. Cumulative reward를 계산하기 위해, 미래의 reward는 discount factor라고 불리우는 $\gamma \in [0, 1]$가 가중되어 reward의 가중합 (weighted sum) 형태로 나타내게 되는데, 이를 주로 return이라고 부른다.

$\mathbf{Definition.}$ Return 
Return $G_t$ is the total discounted reward from timestep $t$:

$$
\begin{align*}
  G_t = R_{t + 1} + \gamma R_{t+2} + \cdots = \sum_{T = 0}^\infty \gamma^T R_{t + T + 1}
\end{align*}
$$

 

하지만 reward function이 deterministic하지 않거나, stochastic environment 등의 조건에서는 똑같은 action을 취하더라도 매 episode마다 return이 달라질 수 있다. 그렇기에 강화학습에서는 추가적으로 value function을 정의하는데, 특정 state에서의 return의 기댓값으로 정의한다.

 

$\mathbf{Definition.}$ Value function
The value function $v(s)$ is defined by the expectation of return at the current state

$$
\begin{align*}
  V(s) = \mathbb{E}[G_t \; | \; S_t = s]
\end{align*}
$$

 

Why a discount factor is needed?

Return과 value에서 discount factor가 특별히 필요한 이유는 다음과 같은 것들이 있다. 

• Mathematically convenient tractable
  • ex. avoid divergence of sum
• preference for immediate reward
• etc. 

Markov Reward Process in graph

Markov Process의 그래프 $\mathbf{Fig\ 1}$는 다음과 같이 Markov Reward Process로 확장될 수 있다. 

$\mathbf{Fig\ 2.}$ Markov reward process

초기 상태 $S_1 = C_1$, discount factor $\gamma = \frac{1}{2}$에 대해 각 state에 대한 return은 다음과 같이 계산된다.

$$
\begin{array}{l|lll}
\text { C1 C2 C3 Pass Sleep } & v_1=-2-2 * \frac{1}{2}-2 * \frac{1}{4}+10 * \frac{1}{8} & = & -2.25 \\
\text { C1 FB FB C1 C2 Sleep } & v_1=-2-1 * \frac{1}{2}-1 * \frac{1}{4}-2 * \frac{1}{8}-2 * \frac{1}{16} & = & -3.125 \\
\text { C1 C2 C3 Pub C2 C3 Pass Sleep } & v_1=-2-2 * \frac{1}{2}-2 * \frac{1}{4}+1 * \frac{1}{8}-2 * \frac{1}{16} \cdots & = & -3.41 \\
\text { C1 FB FB C1 C2 C3 Pub C1 } \ldots & v_1=-2-1 * \frac{1}{2}-1 * \frac{1}{4}-2 * \frac{1}{8}-2 * \frac{1}{16} \cdots & = & -3.20
\end{array}
$$

 

Bellman Equation

강화학습에서 사용되는 Value function의 가장 기본적이고 필수적인 성질은, value function이 특정한 점화식을 만족한다는 것이다.  벨만 방정식 Bellman equation에 따라 value function은 바로 다음 시점의 reward $R_{t + 1}$와 다음 시점 상태의 discounted  value function $\gamma \cdot V (S_{t+1})$, 2가지 파트로 나뉘어질 수 있다. 

$$
\begin{aligned}
  V(s) & =\mathbb{E}\left[G_t \mid S_t=s\right] \\
  & =\mathbb{E}\left[R_{t+1}+\gamma \cdot R_{t+2}+\gamma^2 \cdot R_{t+3}+\ldots \mid S_t=s\right] \\
  & =\mathbb{E}\left[R_{t+1}+\gamma \cdot \left(R_{t+2}+\gamma R_{t+3}+\ldots\right) \mid S_t=s\right] \\
  & =\mathbb{E}\left[R_{t+1}+\gamma \cdot G_{t+1} \mid S_t=s\right] \\
  & =\mathbb{E}\left[R_{t+1}+\gamma \cdot V\left(S_{t+1}\right) \mid S_t=s\right]
\end{aligned}
$$

 

또는 다음과 같이 행렬 형태로 표현될 수 있다. 

$$
\begin{align*}
  V = \mathcal{R} + \gamma \mathcal{P} V
\end{align*}
$$

 

여기서 $V$는 각 state의 value 값으로 이루어직 열 벡터이다. 

$$
\begin{align*}
  \left[\begin{array}{c}
  v(1) \\
  \vdots \\
  v(n)
  \end{array}\right]=\left[\begin{array}{c}
  \mathcal{R}_1 \\
  \vdots \\
  \mathcal{R}_n
  \end{array}\right]+\gamma\left[\begin{array}{ccc}
  \mathcal{P}_{11} & \ldots & \mathcal{P}_{1 n} \\
  \vdots & & \\
  \mathcal{P}_{11} & \ldots & \mathcal{P}_{n n}
  \end{array}\right]\left[\begin{array}{c}
  v(1) \\
  \vdots \\
  v(n)
  \end{array}\right]
\end{align*}
$$

 

수치적으로, 역행렬 방식을 통해 $v = (I - \gamma \mathcal{P})^{-1} \mathcal{R}$로 얻어질 수 있다. 그러나 일반적으로 역행렬 방식은 매우 비효율적으로, 계산 복잡도는 $n$ 상태에 대해 $O(n^3)$이다. 그렇기 때문에, 앞으로 dynamic programming, Monte-Carlo evaluation, Temporal-Difference learning 등 value function을 계산하기 위한 다양한 수치 알고리즘을 살펴볼 것이다. 

RL에서는 벨만 방정식을 주로 Backup diagram으로 시각화하여 표현한다.

 

$\mathbf{Fig\ 3.}$ Backup diagram for Bellman equation in MRP

 

이 diagram은 다음 식과 일치한다.

$$
\begin{aligned}
  v(s) = \mathbb{E}[R_{t+1}] + \gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}} v\left(s^{\prime}\right)
\end{aligned}
$$

 

Backup diagram이라고 불리는 이유는, 이 diagram이 미래 state에서 현재 state의 value function으로 정보를 전송하는 업데이트 방식을 도식화하기 때문이다. 즉 미래 상태에서 현재 상태로 거꾸로 진행되는 backup operation을 보여주는 diagram이기 때문이다. 

Markov Decision Process

이제 agent는 Markov reward process의 environment를 기반으로 행동 (action)을 취할 수 있다. Markov decision process (MDP)는 Markov reward process에 action의 개념을 추가한 것이다. 

 

$\mathbf{Definition.}$ Markov Decision Process 

A Markov Decision Process는 $\left\langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \right\rangle$의 튜플로 나타내며, 각 element는 다음과 같은 특성을 갖는다:

1. $\mathcal{S}$ is a (finite) state space
2. $\mathcal{A}$ is a (finite) action space
3. $\mathcal{P}$ is a state transition probability matrix
   
   $$
   \begin{align*}
     \mathcal{P}_{ss^\prime}^a = P[S_{t+1} = s^\prime | S_t = s, A_t = a]
   \end{align*}
   $$
   
   
4. $\mathcal{R}$ is a reward function
   
   $$
   \begin{align*}
     \mathcal{R}_{s}^a = \mathbb{E} [R_{t+1} | S_t = s, A_t = a]
   \end{align*}
   $$
   
   
5. $\gamma \in [0, 1]$ is a discount factor. 
   
   

유한 공간을 가정하는 이유는 수학적으로 간편하기 때문인데, 적분 기호 $\int$와 확률 밀도가 합 기호 $\Sigma$와 확률로 단순화될 수 있기 때문이다. 물론 연속 공간으로 동일하게 확장될 수 있다. 

 

Policy

그렇다면 agent는 어떻게 행동을 결정할까? 강화학습에서는, 정책 (policy)가 특정 상태에서 어떤 행동을 해야하는지 정의한다.

$\mathbf{Definition.}$ Policy 
A policy $\pi$ is a distribution over actions given states, 

$$
\begin{aligned}
  \pi(a | s) = P(A_t = a | S_t = s)
\end{aligned}
$$

 

Agent는 행동을 결정할 때 오직 policy만을 따르며, MDP의 policy는 오직 현재 state에만 의존한다. 

$$
\begin{aligned}
  A_t \sim \pi (\cdot | S_t) 
\end{aligned}
$$

 

따라서 주어진 MDP $\mathcal{M} = \left\langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \right\rangle$와 policy $\pi$는 모두 Markov property를 갖는다. 

• $S_1, S_2, \cdots$ is a Markov process $$\left\langle \mathcal{S}, \mathcal{P}^\pi \right\rangle $$ <br> 
• $S_1, R_1, S_2, R_2, \cdots$ is a Markov reward process $$\left\langle \mathcal{S}, \mathcal{P}^\pi, \mathcal{R}^\pi, \gamma \right\rangle$$ where
  
  $$
  \begin{aligned}
    \mathcal{P}_{s, s^\prime}^\pi & = \sum_{a \in \mathcal{A}} \pi (a | s) \mathcal{P}_{ss^\prime}^a \\
    \mathcal{R}_{s}^\pi & = \sum_{a \in \mathcal{A}} \pi (a | s) \mathcal{R}_{s}^a 
  \end{aligned}
  $$

State and Action-value functions

MDP에서 시점 $t+1$의 state $S_{t+1}$는 시점 $t$의 state $S_t$와 그에 따른 action $A_t$에 따라 결정되므로,  2가지의 value function이 정의될 수 있다. 

 

$\mathbf{Definition.}$ State value function
The state value function $v_\pi (s)$ of an MDP is the expected return starting from state $s$, and then follwing policy $\pi$: 

$$
\begin{aligned}
  v_\pi (s) = \mathbb{E}_\pi [G_t | S_t = s]
\end{aligned}
$$

 

$\mathbf{Definition.}$ State value function
The action-value function $q_\pi (s, a)$ is the value of taking action $a$ in state $s$; the expected return starting from state $s$, taking action $a$, and then follwing policy $\pi$: 

$$
\begin{aligned}
  q_\pi (s, a) = \mathbb{E}_\pi [G_t | S_t = s, A_t = a]
\end{aligned}
$$

 

Optimal Value function and Policy

이때 모든 policy에 대해 최댓값을 갖는 value function을 최적의 value function으로 정의한다. 즉 최적의 value function은 agent가 MDP에서 만들어낼 수 있는 가장 최선의 결과를 나타낸다. 

$\mathbf{Definition.}$ Optimal state-value function
The optimal state-value function $v_\star (s)$ is the maximum value function over all policies:

$$
\begin{aligned}
  v_\star (s) = \underset{\pi \in \mathcal{\Pi}}{\text{max }} v_\pi (s)
\end{aligned}
$$

 

$\mathbf{Definition.}$ Optimal action-value function
The optimal action-value function $q_\star (s, a)$ is the maximum action-value function over all policies:
$$
\begin{aligned}
  q_\star (s, a) = \underset{\pi \in \mathcal{\Pi}}{\text{max }} q_\pi (s, a)
\end{aligned}
$$

 

따라서 최적의 policy도 자연스럽게 value function을 최대화하는 정책으로 정의될 수 있다. 또한 value function을 바탕으로 여러 policy들을 비교할 수 있게 되는데, 다음과 같은 partial ordering을 정의한다. 

$$
\begin{aligned}
  \pi \geq \pi^\prime \text{ if } v_\pi (s) \geq v_{\pi^\prime} (s) \; \forall s
\end{aligned}
$$

 

물론 수학적으로 최적의 value function과 policy의 존재성과 유일성이 증명되어 있으므로, 존재 여부를 걱정하지 않아도 된다.

$\mathbf{Theorem.}$ For any Markov Decision Process, <br>
- There exists an optimal policy $\pi_\star$ that is better than or equal to all other polices, i.e., $\pi_\star \geq \pi \; \forall \pi$. 
- All optimal policies achieve the optimal value function, i.e., $v_{\pi_\star} (s) = v_\star (s)$.
- All optimal policies achieve the optimal action-value function, i.e., $q_{\pi_\star} (s, a) = q_\star (s, a)$. 

And, an optimal policy can be found by maximising over $q_\star(s, a)$, 

$$
\begin{aligned}
  \pi_*(a \mid s)= \begin{cases}1 & \text { if } a=\underset{a \in \mathcal{A}}{\operatorname{argmax}} q_*(s, a) \\ 0 & \text { otherwise }\end{cases}
\end{aligned}
$$

 

 즉 MDP에 대해서 deterministic optimal policy가 항상 존재한다.

 

Bellman Expectation Equations

앞서 보았듯이, value function은 Bellman Equation이라고 불리우는 점화식의 형태로 표현될 수 있었다. State-value 및 action-value function 역시 immediate reward $R_{t+1}$와 discounted value of successor state로 나뉠 수 있다. 

$$
\begin{aligned}
  v_\pi (s) & = \mathbb{E}_\pi [R_{t+1} + \gamma v_\pi (S_{t+1}) | S_t = s] \\
  q_\pi (s, a) & = \mathbb{E}_\pi [R_{t+1} + \gamma q_\pi (S_{t+1}, A_{t+1}) | S_t = s, A_t = a]
\end{aligned}
$$

이때 $v_\pi$의 정의에 따라 다음과 같이 정리될 수 있다. 이를 Bellman expectation equation이라고 한다. 

$$
\begin{aligned}
  v_\pi (s) & = \mathbb{E}_\pi [G_t | S_t = s] \\
  & = \int x \cdot P(G_t = x | S_t = s) \cdot dx \\
  & = \int x \cdot \frac{P(G_t = x \cap S_t = s)}{P(S_t = s)} \cdot dx \\
  & = \int \int_{\mathcal{A}} x \cdot \frac{P(G_t = x \cap S_t = s \cap A_t = a)}{P(S_t = s)} \cdot da \cdot dx \\
  & = \int \int_{\mathcal{A}} x \cdot \frac{P(G_t = x \cap S_t = s \cap A_t = a)}{P(S_t = s \cap A_t = a)} \cdot \frac{P(S_t = s \cap A_t = a)}{P(S_t = s)} \cdot da \cdot dx \\
  & = \int \int_{\mathcal{A}} x \cdot P(G_t = x | S_t = s, A_t = a) \cdot \pi(a | s) \cdot da \cdot dx \\
  & = \sum_{a \in \mathcal{A}} \pi(a | s) \cdot \mathbb{E}_\pi [G_t | S_t = s, A_t = a] = \sum_{a \in \mathcal{A}} \pi(a | s) \cdot q_\pi (s, a).
\end{aligned}
$$

마지막 줄은 action space가 유한하다는 가정 하에 도출된 것이다. MRP의 Bellman equation처럼 backup diagram으로 나타낼 수 있다. 

 

$\mathbf{Fig\ 4.}$ Backup diagram of Bellman expectation equation for $v_\pi$

동일하게 $q_\pi$의 경우

$$
\begin{aligned}
  q_\pi (s) & = \mathbb{E}_\pi [G_t | S_t = s, A_t = a] \\
  & = \mathbb{E}_\pi [R_{t+1} | S_t = s, A_t = a] + \gamma \mathbb{E}_\pi [G_{t + 1} | S_t = s, A_t = a] \\
  & = \mathcal{R}_s^a + \gamma \int x \cdot P(G_{t+1} = x | S_t = s, A_t = a) \cdot dx \\
  & = \mathcal{R}_s^a + \gamma \int x \cdot P(G_{t+1} = x | S_t = s, A_t = a) \cdot dx \\
  & = \mathcal{R}_s^a + \gamma \int x \cdot \frac{P(G_{t+1} = x \cap S_t = s, A_t = a)}{P(S_t = s, A_t = a)} \cdot dx \\
  & = \mathcal{R}_s^a + \gamma \int \int_\mathcal{S} x \cdot \frac{P(G_{t+1} = x \cap S_t = s, A_t = a \cap S_{t+1} = s^\prime)}{P(S_t = s, A_t = a)} \cdot ds^\prime \cdot dx \\
  & = \mathcal{R}_s^a + \gamma \int \int_\mathcal{S} x \cdot \frac{P(G_{t+1} = x \cap S_t = s, A_t = a, S_{t+1} = s^\prime)}{P(S_t = s, A_t = a, S_{t+1} = s^\prime)} \cdot P(S_{t+1} = s^\prime | S_t = s, A_t = a) \cdot ds^\prime \cdot dx \\
  & = \mathcal{R}_s^a + \gamma \int \int_\mathcal{S} x \cdot \frac{P(G_{t+1} = x \cap S_t = s, A_t = a, S_{t+1} = s^\prime)}{P(S_t = s, A_t = a, S_{t+1} = s^\prime)} \cdot P(S_{t+1} = s^\prime | S_t = s, A_t = a) \cdot ds^\prime \cdot dx \\
  & = \mathcal{R}_s^a + \gamma \int \int_\mathcal{S} x \cdot P(G_{t+1} = x | S_t = s, A_t = a, S_{t+1} = s^\prime) \cdot P(S_{t+1} = s^\prime | S_t = s, A_t = a) \cdot ds^\prime \cdot dx \\
  & = \mathcal{R}_s^a + \gamma \sum_{s^\prime \in \mathcal{S}} \mathcal{P}_{ss^\prime}^a \cdot \mathbb{E}_\pi [G_{t+1} | S_{t+1} = s^\prime] = \mathcal{R}_s^a + \gamma \sum_{s^\prime \in \mathcal{S}} \mathcal{P}_{ss^\prime}^a \cdot v_\pi (s^\prime).
\end{aligned}
$$

 

역시 마지막 줄은 state space가 유한하다는 가정과 Markov 성질에 의해 도출되었다. 

 

$\mathbf{Fig\ 5.}$ Backup diagram of Bellman expectation equation for $q_\pi$

 

두 방정식은 이중 점화식이기 때문에, 연립방정식을 통해 더 간단한 형태로 정리할 수 있을 것이다. 대입을 통해 식을 정리하면 다음과 같다.

$$
\begin{aligned}
  v_\pi(s) & =\sum_{a \in \mathcal{A}} \pi(a \mid s)\left(\mathcal{R}_s^a+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^a v_\pi\left(s^{\prime}\right)\right) \\
  q_\pi(s, a) & =\mathcal{R}_s^a+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^a \sum_{a^{\prime} \in \mathcal{A}} \pi\left(a^{\prime} \mid s^{\prime}\right) q_\pi\left(s^{\prime}, a^{\prime}\right)
\end{aligned}
$$

 

$\mathbf{Fig\ 6.}$ Backup diagram of Bellman expectation equations

 

Bellman Optimality Equations

결국 MDP의 최종 목표는 value function을 최대화하는 최적의 policy $\pi_\star$를 찾는 것이다. 이때  $\pi_\star (a | s) = \underset{a \in \mathcal{A}}{\text{ arg max }} q_{\pi_\star} (s, a)$이므로, $v_{\pi_\star} (s) = \sum_{a \in \mathcal{A}} \pi_\star (a | s) q_{\pi_\star} (s, a)$에서 $v_{\pi_\star} (s) = \underset{a \in \mathcal{A}}{\text{max }} q_\star (s, a)$임은 자명하다. 따라서, 최종적으로 optimal value function들은 Bellman expectation equation에서와 같이 서로 점화식 형태로 연관이 되어 있는데, 이를 Bellman optimality equation이라고 한다.

$$
\begin{aligned}
  v_\star (s) & = \underset{a \in \mathcal{A}}{\text{max }} q_\star (s, a) \\
  q_\star (s, a) & = \mathcal{R}_s^a + \gamma \sum_{s^\prime \in \mathcal{S}} \mathcal{P}_{ss^\prime}^a v_\star (s^\prime)
\end{aligned}
$$

 

$\mathbf{Fig\ 7.}$ Backup diagram of Bellman optimality equations

 

이때 대입을 통해 이중 점화식을 풀어주면 다음과 같은 관계가 도출된다. 

$$
\begin{aligned}
  v_\star (s) & = \underset{a \in \mathcal{A}}{\text{max }} [\mathcal{R}_s^a + \gamma \sum_{s^\prime \in \mathcal{S}} \mathcal{P}_{ss^\prime}^a v_\star (s^\prime)] \\
  q_\star (s, a) & = \mathcal{R}_s^a + \gamma \sum_{s^\prime \in \mathcal{S}} \mathcal{P}_{ss^\prime}^a \underset{a^\prime \in \mathcal{A}}{\text{ max }} q_\star (s^\prime, a^\prime)
\end{aligned}
$$

 

$\mathbf{Fig\&nbsp;9.}$&nbsp;Backup&nbsp;diagram&nbsp;of&nbsp;Bellman&nbsp;optimality&nbsp;equations

 

Bellman Optimality equation은 비선형적이므로, 일반적으로 닫힌 형태의 해가 존재하지 않는다. 그렇기 때문에 dynamic programming (value iteration, policy iteration 등), Q-learning, SARSA 등 다양한 알고리즘을 통해 수치적 해를 얻게 된다. 이러한 알고리즘은 Bellman Optimality equation을 풀기 위해 고안된 것들로, Bellman equation을 기반으로 하므로 위의 방정식들을 잘 기억해두자. Bellman equation을 총정리하며 글을 마무리한다. 

$\mathbf{Fig\&nbsp;10.}$&nbsp;Summary&nbsp;of&nbsp;Bellman&nbsp;equations&nbsp;in&nbsp;MDP

 

Reference

[1] Reinforcement Learning: An Introduction. Richard S. Sutton and Andrew G. Barto, The MIT Press.

[2] Introduction to Reinforcement Learning with David Silver

[3] Introduction to Reinforcement Learning by Maël Fabien

[4] A (Long) Peek into Reinforcement Learning