CS234의 Markov Decision Process에 대한 강의 요약
이번 장이 끝날 때 까지 간결함을 위해 깨지지 않을 ASSUMPTION :
- finite state space
- stationary transition probability
- stationary reward
- stationary policy
- $\gamma < 1$
- Model
- environment의 dynamics와 agent에게 줄 reward에 대한 명시이다.
- $P(s’, r’ \mid s, a)$
- 보통 Transition probability $P(s’ \mid s, a)$ 와 reward $R(s, a)$에 대한 명시이다.
- Policy
- $\pi : S \rightarrow A$
- stochastic or deterministic
- Markov Property
- $P\left(s_{i} \mid s_{0}, \ldots, s_{i-1}\right)=P\left(s_{i} \mid s_{i-1}\right)$
- Horizon
- The number of time steps in the realization of a process
- $H$
- Markov decision process
- realization : $\left(s_{0}, a_0, r_{0}, \quad s_{1}, a_1, r_{1}, \quad \ldots, s_{H-1}, a_{H-1}, r_{H-1}, \quad s_H\right)$
- transition probability $P\left(s_{i}=s^{\prime} \mid s_{i-1}=s, a_{i-1}=a\right)=P\left(s_{j}=s^{\prime} \mid s_{j-1}=s, a_{j-1}=a\right)$
- reward function $R: S \times A\rightarrow \mathbb R$ s.t.$\quad R(s, a)=\mathbb{E}\left[r_{i} \mid s_{i}=s, a_i = a\right]$
- discount factor $\gamma \in [0, 1]$
- Return
- $G_{t}=\sum_{i=t}^{H-1} \gamma^{i-t} r_{i}, \forall 0 \leq t \leq H-1$
- State value function
- 특정 policy $\pi$를 가진 agent가 $s$에서 시작했을 때 받게 될 reward의 기대값
- $V^\pi_t : S \rightarrow \mathbb R$ s.t. $\quad V_{t}^{\boldsymbol{\pi}}(s)=\mathbb{E}\left[G_{t} \mid s_{t}=s\right]$
- Infinite horizon일 경우
- $V^{\pi}(s) = R^\pi (s) +\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s\right) V^{\pi}\left(s^{\prime}\right)$ where $\begin{aligned}
R^{\pi}(s) &=\sum_{a \in A} \pi(a \mid s) R(s, a) \\
P^{\pi}\left(s^{\prime} \mid s\right) &=\sum_{a \in A} \pi(a \mid s) P\left(s^{\prime} \mid s, a\right)
\end{aligned}$
- $V^{\pi}(s) = R^\pi (s) +\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s\right) V^{\pi}\left(s^{\prime}\right)$ where $\begin{aligned}
- State-action value function
- 특정 policy $\pi$를 가진 agent가 $s$에서 시작해 $a$를 했을 때 받게 될 reward의 기대값
- $Q_{t} : S \times A \rightarrow \mathbb R $s.t. $\quad Q_{t}^{\boldsymbol{\pi}}(s, a)=\mathbb{E}\left[G_{t} \mid s_{t}=s, a_{t}=a\right]$
- Infinite horizon일 경우
- $Q^{\pi}(s, a) = R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) V^{\pi}\left(s^{\prime}\right)$
Infinite horizon setting에서 $\gamma < 1$이라면 Iterative algorithm으로 MDP의 value function을 구할 수 있다.
이의 증명을 위해 Bellman backup operator를 정의하겠다.
3.5 Bellman backup operators
3.5.1 Bellman expectation backup operator
Value function은 finite dimensional Banach space $\mathbb R^{|S|}$ with infinity norm상의 원소이다.
이 space에서 Bellman expectation backup operator를 정의하겠다.
이는 $\gamma <1$인 경우에 contraction map이 되기에 unique한 fixed point $V^\pi (s)$를 갖는다.
3.5.2 Bellman optimality backup operator
Optimal value function은 finite dimensional Banach space $\mathbb R^{|S|}$ with infinity norm상의 원소이다.이
이 space에서 Bellman optimality backup operator를 정의하겠다.
이는 $\gamma <1$인 경우에 contraction map이 되기에 unique한 fixed point $V^{\pi^*} (s)$를 갖는다.
3.6 MDP control in the infinite horizon setting
MDP에선 optimal policy search에 stationary policy만 고려해도 됨을 예제 3.18에서 보였다.
Theorem 3.8 (Bellman optimality backup operator의 적용)
Let $\pi$ be a given stationary policy
Then, there exists a deterministic stationary policy $\hat \pi$ s.t. $V^{\hat \pi}(s) \geq V^\pi(s)$.
One such policy $\hat \pi$ is given by
, satisfying $\left(B^{\hat{\pi}} V^{\pi}\right)(s)=\left(B^{*} V^{\pi}\right)(s) \geq V^{\pi}(s)$
Moreover, $V^{\hat{\pi}}(s)=V^{\pi}(s)$ i.f.f. $\left(B^{*} V^{\pi}\right)(s)=V^{\pi}(s)$
즉, Bellman optimality backup operator의 fixed point가 optimal value function이다.
3.6.1 Policy search
브루트포스 알고리즘으로 $|A| ^S$개의 deterministic policy를 비교하여 최적의 policy를 찾는다.
3.6.2 Policy Iteration
Theorem 3.8에 근거한 policy improvement algorithm을 생각할 수 있다.
Policy iteration 알고리즘은 policy search보다 더 효율적인 알고리즘이다.
Policy improvement로 policy를 업데이트하게 된다.
3.6.3 Value Iteration
Theorem 3.10 (Bellman optimality backup operator)
Let $V^\star$ be the fixed point of the Bellman optimality backup operator $B^{\star}$
Let $\pi ^\star (s) := \underset{a \in A}{\arg \max }\left[R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s, a\right) V^{*}\left(s^{\prime}\right)\right]$.
Then, the deterministic policy $\pi^*$ is an optimal policy.
Theorem 3.10에 기반하여 policy evaluation에서 fixed point를 구하고 난 뒤에 그걸로 optimal policy를 구한다.