1. 정의

1.1 마르코프 결정 프로세스(MDP)

state( $\mathbf{x}_t$ ), State Transition Probability Density Function($p$)와 행동($\mathbf{a}_t$), reward function($r(\mathbf{x}_t, \mathbf{a}_t)$ )로 이루어진 이산시간 확률 프로세스(discrete time stochastic process)로서,
순차적으로 action을 결정해야 하는 문제를 풀기 위한 수학 모델.

여기서 state( $\mathbf{x}_t$ ), 행동($\mathbf{a}_t$)은 연속공간이거나 이산공간 랜덤 변수다.

1.2 마르코프 시퀀스

State Transition PDF ( $p$ )

state와 action이 연속공간 변수라면 어떤 state( $\mathbf{x}_t$ )에서 agent가 행동($\mathbf{a}_t$)을 선택했을 때 다음 state( $\mathbf{x}_t$ )로 갈 PDF는 다음과 같이 표현
$p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{a}_t)$

state와 action이 이산공간 변수라면 State Transition PDF는 다음과 같이 표현
$\mathbf{P} \{ \mathbf{x}_{t+1}| \mathbf{x}_{t}, \mathbf{a}_t \}$

state transition function를 미래의 state가 과거의 state와 action에 관계없이 현재 state와 action에만 영향을 받도록 정의
-> 이러한 process를 마르코프 시퀀스라고 한다.

즉 마르코프 시퀀스는 미래의 state를 알기 위해 현재의 state와 action 정보만 필요하며 과거의 history와는 관계없는 sequence.
$p(\mathbf{x}_{t+1}|\mathbf{x}_{t}, \mathbf{x}_{t-1}, ... , \mathbf{x}_{0}, \mathbf{a}_{t}, \mathbf{a}_{t-1}, \mathbf{a}_{0}) = p(\mathbf{x}_{t+1})$

1.3 MDP 목표

reward function

$r(\mathbf{x}_t, \mathbf{a}_t)$는 어떤 state( $\mathbf{x}_t$ )에서 agent가 action($\mathbf{a}_t$)를 선택했을 때 즉시 받을 수 있는 reward. reward는 랜덤 변수로서 환경에서 주어짐.

MDP 목표는 누적된 reward를 가장 많이 획득하기 위해 각 state에서 어떤 action을 취할 것인가 나타내는 conditional PDF를 구하는 것.

$\pi(\mathbf{a}_t| \mathbf{x}_t)=p(\mathbf{a}_t |\mathbf{x}_t)$

즉 $\pi$ 라는 정책을 구하는 것.

Trajectory

Trajectory는 state 변수와 action의 연속적인 시퀀스로 구성
$\tau=(\mathbf{x}_0, \mathbf{a}_0, \mathbf{x}_1,\mathbf{a}_1, \mathbf{x}_2,\mathbf{a}_2, ..., \mathbf{x}_T, \mathbf{a}_T)$

1. state 변수 $\mathbf{x}_0$에서 어떤 정책 $\pi$에 의해 $\mathbf{a}_0$가 확률적으로 선택(Sampling)되면 State Transition PDF에 의해 상태변수 $\mathbf{x}_1$으로 이동
2. 이때 환경에 의해 보상 $r(\mathbf{x}_0, \mathbf{a}_0)$ 주어짐
3. 다시 state 변수 $\mathbf{x}_1$에서 $\mathbf{u}_1$이 Sampling되면 State Transition PDF에 의해 상태변수 $\mathbf{x}_2$로 이동.
4. 이때 환경에 의해 $r(\mathbf{x}_1, \mathbf{a}_1)$ 주어짐
5. 위 과정 반복되어 state, action, reward의 순서로 전개

위와 같이 Environment 모델이 State Transition PDF로 주어지면 확률적 MDP라고 함.
Environment 모델과 정책이 모두 확정적으로 주어졌다면 확정적 MDP라고 한다.
확정적 MDP에서는 환경 모델이 다음과 같이 주어짐.
$\mathbf{x}_{t+1}=\mathbf{f}(\mathbf{x}_t, \mathbf{a}_t)$
즉, t에서 state와 action이 주어지면 다음 state $\mathbf{x}_{t+1}$을 확정적으로 알 수 있다.
확정적 MDP에서 reward가 $r(x_t, a_t)$로 주어지고, 정책은 state 변수에서 action을 직접 계산하는 함수
$u_t = \pi(\mathbf{x}_t)$. 이 정책을 확정적 정책.

discounted return(반환값)

t 이후 미래에 얻을 수 있는 reward 총합은 아래와 같다.

$G_t = r(\mathbf{x}_t,\mathbf{a}_t)+\gamma*r(\mathbf{x}_{t+1},\mathbf{a}_{t+1})+\gamma^2*r(\mathbf{x}_{t+2},\mathbf{a}_{t+2})+...+\gamma^{T-t}*r(\mathbf{x}_{T},\mathbf{a}_{T})$
= $\sum^T_{k=t}\gamma^{k-t}*r(\mathbf{x}_k,\mathbf{a}_k)$

$\gamma$는 discount factor( $0\le\gamma\le1$ )

reward가 랜덤 변수이기 때문에 discounted return 값 역시 랜덤 변수.
하지만, 확정적 MDP라면 discounted return은 확정된 값.
discount factor의 값이 작을수록 agent가 먼 미래에 받을 reward보다 가까운 미래에 받을 reward에 더 큰 가중치를 둠

discount factor는 $T → \infin$일 때 discounted return이 무한대로 발산하는 것을 막는 수학적 장치
즉, $0\le\gamma<1$이면 다음 식이 성립하므로 $T → \infin$이더라도 discounted reward는 유한한 값을 가짐.

$|G_t|=|\sum_{k=t}^{\infin}\gamma^{k-t}*r(\mathbf{x}_k,\mathbf{a}_k)|\le \sum_{k=t}^{\infin}\gamma^{k-t}*|r(\mathbf{x}_k,\mathbf{a}_k)|$

$\le r_{max} \sum^{\infin}_{k=0}\gamma^k = \frac{r_{max}}{1-\gamma}$
임의의 k에 대해 $|r(\mathbf{x}_k,\mathbf{a}_k)| \le r_{max}$ 성립

Episode: state, action, reward의 시퀀스 집합
유한 구간 Episode: 특정 state에 도달하면 종료됨
무한 구간 Episode: $t=T→\infin$ 무한히 이어짐

---

2. Value function

State-Value(상태 가치)

어떤 state 변수 $\mathbf{x}_t$에서 시작하여 정책 $\pi$에 의해서 action이 가해졌을 때 기대할 수 있는 discounted reward
$V^\pi(\mathbf{x}_t)=\mathbb{E}_{\tau_{a_t:a_T} \sim {} p(\tau_{a_t:a_T}|\mathbf{x}_t)}\mathbf{[}\sum^T_{k=t}\gamma^{k-t}r(\mathbf{x}_k,\mathbf{a}_k)|\mathbf{x}_t]$
$=\int_{\tau_{a_t}:\tau_{a_T}}(\sum^T_{k=t}\gamma^{k-t}r(\mathbf{x}_k,\mathbf{a}_k))*p(\tau_{a_t:a_T}|\mathbf{x}_t)d\tau_{a_t:a_{T}}$

해석: 상태 $\mathbf{x}_t$에서 $\mathbf{u}_t$에서 $\mathbf{u}_T$까지 일련의 action을 택하면서 얻는 discounted reward이다. 이 기댓값을 계산할 때 Trajectory인 $\tau$에서 $\mathbf{x}_t$일 때 확률밀도 함수 state transition PDF($p(\tau_{a_t:a_T}|\mathbf{x}_t)$)를 사용한다는 의미

Action-value(행동 가치)

어떤 상태변수 $\mathbf{x}_t$에서 행동 $\mathbf{a}_t$를 선택하고 그로부터 정책 $\pi$에 의해서 행동이 가해지면 기대할 수 있는 미래의 discounted reward의 기댓값
$Q^{\pi}(\mathbf{x}_t,\mathbf{a}_t)=\mathbb{E}_{\tau_{\mathbf{x}_{t+1}:a_T} \sim {} p(\tau_{\mathbf{x}_{t+1}:a_T}|\mathbf{x}_t, \mathbf{a}_t)}\mathbf{[}\sum^T_{k=t}\gamma^{k-t}r(\mathbf{x}_k,\mathbf{a}_k)|\mathbf{x}_t,\mathbf{a}_t]$

$=\int_{\tau_{\mathbf{x}_{t+1}}:\tau_{a_T}}(\sum^T_{k=t}\gamma^{k-t}r(\mathbf{x}_k,\mathbf{a}_k))*p(\tau_{\mathbf{x}_{t+1}:a_T}|\mathbf{x}_t,\mathbf{a_t})d\tau_{\mathbf{x}_{t+1}:a_{T}}$

해석: 상태 $\mathbf{x}_t$에서 이미 action $\mathbf{a}_t$를 취하고 $\mathbf{x}_{t+1}$에서 $\mathbf{a}_T$까지 일련의 action을 택하면서 얻는 discounted reward이다. 이 기댓값을 계산할 때 Trajectory인 $\tau$에서 $\mathbf{a}_t$일 때 확률밀도 함수 state transition PDF($p(\tau_{\mathbf{x}_{t+1}:\mathbf{a_T}}|\mathbf{x}_t,\mathbf{a}_t)$)를 사용한다는 의미

State-Value와 Action-Value 간의 관계

$\tau_{a_t:a_T}=(\mathbf{a}_t, \mathbf{x}_{t+1}, \mathbf{a}_{t+1},...,\mathbf{a}_T)$
$=(\mathbf{a}_t) \cap (\mathbf{x}_{t+1}, \mathbf{a}_{t+1},...,\mathbf{a}_T)$
$=(\mathbf{a}_t) \cap \tau_{\mathbf{x}_{t+1}:\mathbf{a}_T}$

확률의 chain rule, $p_{XY|Z}(x,y|z)=p_{X|Y,Z}(x|y,z)*p_{Y|Z}(y|z)$에 의해

$p(\tau_{\mathbf{a}_t:\mathbf{a}_T}|\mathbf{x}_t)=p(\mathbf{a}_t, \tau_{\mathbf{x}_{t+1}:\mathbf{a}_t}|\mathbf{x}_t)$
$=p(\tau_{\mathbf{x}_{t+1}:\mathbf{a}_t}|\mathbf{x}_t,\mathbf{a}_t)*p(\mathbf{a}_t|\mathbf{x}_t)$
$=p(\tau_{\mathbf{x}_{t+1}:\mathbf{a}_t}|\mathbf{x}_t,\mathbf{a}_t)*\pi(\mathbf{a}_t|\mathbf{x}_t)$

위 식을 Value-Function에 대입하면,
$V^\pi(\mathbf{x}_t)=\int_{\tau_{a_t}:\tau_{a_T}}(\sum^T_{k=t}\gamma^{k-t}r(\mathbf{x}_k,\mathbf{a}_k))*p(\tau_{a_t:a_T}|\mathbf{x}_t)d\tau_{a_t:a_{T}}$
$=\int_{\tau_{a_t}}\int_{\tau_{\mathbf{x}_{t+1}}:\tau_{a_T}}(\sum^T_{k=t}\gamma^{k-t}r(\mathbf{x}_k,\mathbf{a}_k))*p(a_t, \tau_{\mathbf{x}_{t+1}:a_T}|\mathbf{x}_t)d\tau_{\mathbf{x}_{t+1}:a_{T}}d\tau_{a_t}$

$=\int_{\tau_{a_t}}\int_{\tau_{\mathbf{x}_{t+1}}:\tau_{a_T}}(\sum^T_{k=t}\gamma^{k-t}r(\mathbf{x}_k,\mathbf{a}_k))*p( \tau_{\mathbf{x}_{t+1}:a_T}|\mathbf{x}_t,a_t)*\pi(a_t|\mathbf{x}_t)\ d\tau_{\mathbf{x}_{t+1}:a_{T}} d\tau_{a_t}$

$=\int_{a_t} [ \int_{\tau_{\mathbf{x}_{t+1}}:\tau_{a_T}}(\sum^T_{k=t}\gamma^{k-t}r(\mathbf{x}_k,\mathbf{a}_k))*p( \tau_{\mathbf{x}_{t+1}:a_T}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:a_{T}} ] \pi(a_t|\mathbf{x}_t)\ da_t$

$V^\pi(s)=\int_{a_t}Q^\pi(\mathbf{x}_t,a_t)\pi(a_t|\mathbf{x}_t)da$
$=\mathbb{E}_{a_t\sim\pi(a_t|\mathbf{x}_t)}[Q^\pi(\mathbf{x}_t, a_t)]$

State-Value는 상태변수 $\mathbf{x}_t$에서 선택 가능한 모든 행동 $a_t$에 대한 Action-Value의 평균값이다.

---

3. Bellman Equation

Value Function을 시간 구간 $[t, t+n-1]$에서 전개. $t+n \le T$이고, $r_i=r(\mathbf{x}_i,a_i)$

$Q^\pi(\mathbf{x}_t, \mathbf{a}_t)=\int_{\tau_{\mathbf{x}_{t+1}:a_T}}(\sum^T_{k=t}\gamma^{k-t}r_k)*p(\tau_{\mathbf{x}_{t+1}:a_T}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:a_T}$

$=\int_{\tau_{\mathbf{x}_{t+1}:a_T}}(r_t+\gamma*r_{t-1}+...+\gamma^{n-1}*r_{t+n-1}+\sum^T_{k=t+n}\gamma^{k-1}r_k)*p(\tau_{\mathbf{x}_{t+1}:a_T}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:a_T}$

$=\int_{\tau_{\mathbf{x}_{t+1}:a_T}}(r_t+\gamma*r_{t-1}+...+\gamma^{n-1}*r_{t+n-1})p(\tau_{\mathbf{x}_{t+1}:a_T}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:a_T} + \int_{\tau_{\mathbf{x}_{t+1}:a_T}}(\sum^T_{k=t+n}\gamma^{k-1}r_k)*p(\tau_{\mathbf{x}_{t+1}:a_T}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:a_T}$

$=Q_1+Q_2$

trajectory $\tau_{\mathbf{x}_{t+1}:a_T}$ 는 다음과 같이 분할할 수 있다.
$\tau_{\mathbf{x}_{t+1}:a_T}=(\mathbf{x}_{t+1}, a_{t+1}, \mathbf{x}_{t+2}, a_{t+2}, ..., \mathbf{x_{T}}, a_T)$
$=\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}\cup \tau_{\mathbf{a}_{t+n}:a_{T}}$

확률의 chain rule에 의해
$p(\tau_{\mathbf{a}_t:\mathbf{a}_T}|\mathbf{x}_t, a_t)=p(\tau_{\mathbf{x}_{t+1}:x_{t+n}}, \tau_{\mathbf{a}_{t+n}:\mathbf{a}_T}|\mathbf{x}_t, a_t)$
$=p(\tau_{\mathbf{a}_{t+n}:\mathbf{a}_{T}}|\mathbf{x}_t,\mathbf{a}_t, \tau_{\mathbf{x}_{t+1}:x_{t+n}})*p(\tau_{\mathbf{x}_{t+1}:x_{t+n}}|\mathbf{x}_t,a_t)$

$Q_1$

$=\int_{\tau_{\mathbf{x}_{t+1}:a_T}}(r_t+\gamma*r_{t-1}+...+\gamma^{n-1}*r_{t+n-1})p(\tau_{\mathbf{x}_{t+1}:a_T}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:a_T}$

$=\int_{\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}}\int_{\tau_{\mathbf{a}_{t+n}:a_T}}(r_t+\gamma*r_{t-1}+...+\gamma^{n-1}*r_{t+n-1})p(\tau_{\mathbf{x}_{t+1}:a_T}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:a_T}$
$=\int_{\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}}\int_{\tau_{\mathbf{a}_{t+n}:a_T}}(r_t+\gamma*r_{t-1}+...+\gamma^{n-1}*r_{t+n-1})p(\tau_{\mathbf{a}_{t+1}:\mathbf{a}_{t+n}}|\mathbf{x}_t,a_t, \tau_{\mathbf{x}_{t+n}:\mathbf{x}_T})d\tau_{\mathbf{a}_{t+1}:\mathbf{a}_{t+n}}p(\tau_{\mathbf{x}_{t+n}:\mathbf{x}_T}|\mathbf{x}_t,a_t) d\tau_{\mathbf{x}_{t+n}\mathbf{x}_{T}}$

$=\int_{\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}}[\int_{\tau_{\mathbf{a}_{t+n}:a_T}}p(\tau_{a_{t+n}:a_T}) d\tau_{\mathbf{a}_{t+n}:\mathbf{a}_{T}} ](r_t+\gamma*r_{t-1}+...+\gamma^{n-1}*r_{t+n-1})p(\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}$
$=\int_{\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}}(r_t+\gamma*r_{t-1}+...+\gamma^{n-1}*r_{t+n-1})p(\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}$

$Q_2$

$=\int_{\tau_{\mathbf{x}_{t+1}:a_T}}(\sum^T_{k=t+n}\gamma^{k-t}r_k)*p(\tau_{\mathbf{x}_{t+1}:a_T}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:a_T}$
$=\int_{\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}}\gamma^n[\int_{\tau_{a_{t+n}:a_T}}(\sum^T_{k=t+n}\gamma^{k-t-n}*r(\mathbf{x}_k,\mathbf{a}_k))*p(\tau_{a_{t+n}:a_T}|\mathbf{x}_t, \mathbf{a}_t, \tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}})d\tau_{a_{t+n}:a_T}]\ p(\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}$

MDP라고 가정하면 $p(.|\mathbf{x}_t, \mathbf{a}_t, \tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}})=p(.|\mathbf{x}_{t+n})$

$=\int_{\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}}\gamma^n[\int_{\tau_{a_{t+n}:a_T}}(\sum^T_{k=t+n}\gamma^{k-t-n}*r(\mathbf{x}_k,\mathbf{a}_k))*p(\tau_{a_{t+n}:a_T}|\mathbf{x}_{t+n})d\tau_{a_{t+n}:a_T}]\ p(\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}$

State-Value function 정의는
$V^\pi(\mathbf{x}_t)=\int_{\tau_{a_t}:\tau_{a_T}}(\sum^T_{k=t}\gamma^{k-t}r(\mathbf{x}_t, a_t))*p(\tau_{a_t:a_T}|\mathbf{x}_t)d\tau_{a_t:a_T}$

$Q_2=\int_{\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}}\gamma^n*V^\pi(\mathbf{x}_{t+n})*p(\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}$

$Q=Q_1+Q_2$

$Q^{\pi}(\mathbf{x}_t, a_t)=\int_{\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}}(r_t+\gamma*r_{t-1}+...+\gamma^{n-1}*r_{t+n-1})p(\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}} +\int_{\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}}\gamma^n*V^\pi(\mathbf{x}_{t+n})*p(\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}$

$=\int_{\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}}[(r_t+\gamma*r_{t-1}+...+\gamma^{n-1}*r_{t+n-1} +\gamma^n*V^\pi(\mathbf{x}_{t+n}))]*p(\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}|\mathbf{x}_t,a_t)d\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}$

$=\mathbb{E}_{\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}} \sim p(\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}|\mathbf{x}_t,a_t)}[\ r_t+\gamma*r_{t-1}+...+\gamma^{n-1}*r_{t+n-1} +\gamma^n*V^\pi(\mathbf{x}_{t+n})]$

식 $V^{\pi}(\mathbf{x}_t)=\int_{u_t}Q^\pi(\mathbf{x}_t,a_t)\pi(a_t|\mathbf{x}_t)da_t$ 에 위의 $Q^{\pi}(\mathbf{x}_t, a_t)$ 전개식을 대입하면

$V^{\pi}(\mathbf{x}_t)=\int_{a_t}\pi(a_t|\mathbf{x}_t)[ \int_{\tau_{\mathbf{x}_{t+1}}:\mathbf{x}_{t+n}}[r_t+...+\gamma^n*V^{\pi}(\mathbf{x}_{t+n})]*p(\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}|\mathbf{x}_t, a_t) d\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}] da_t$

확률의 chain rule, $p_{XY|Z}(x,y|z)=p_{X|Y,Z}(x|y,z)*p_{Y|Z}(y|z)$에 의해
$p(\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}}|\mathbf{x}_t, a_t)=\cfrac{p(\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}, a_t}|\mathbf{x}_t)}{\pi(a_t|\mathbf{x}_t)}$ 를 대입하면

$=\int_{a_t}[ \int_{\tau_{\mathbf{a}_{t}}:\mathbf{x}_{t+n}}[r_t+...+\gamma^n*V^{\pi}(\mathbf{x}_{t+n})]*p(\tau_{\mathbf{x}_{t+1}:\mathbf{x}_{t+n}, a_t}|\mathbf{x}_t) d\tau_{\mathbf{a}_{t}:\mathbf{x}_{t+n}}] da_t$

$=\int_{\tau_{a_t}:\mathbf{x}_{t+n}}[r_t+\gamma*r_{t+1}+...+\gamma^{n-1}*r_{t+n-1}+\gamma^n*V^{\pi}(\mathbf{x_{t+n}})]*p(\tau_{\mathbf{a}_{t}:\mathbf{x}_{t+n}}|\mathbf{x}_t) d\tau_{\mathbf{a}_{t}:\mathbf{x}_{t+n}}$
$=\mathbb{E}_{\tau_{\mathbf{a}_t}:\tau_{\mathbf{x}_{t+n}}\sim p(\tau_{a_t:\mathbf{x}_t}|\mathbf{x}_t)}[r_t+\gamma*r_{t+1}+...+\gamma^{n-1}*r_{t+n-1}+\gamma^n{V^{\pi}(\mathbf{x}_{t+n})}]$
위의 궤적은 어떤 상태변수 $\mathbf{x_t}$에서 시작해 정책 $\pi$로 생성된 궤적이다.
시간구간 n=1로 하면,
$V^{\pi}(\mathbf{x}_t)=\int_{a_t}\pi(a_t|\mathbf{x}_t)[\int_{\mathbf{x}_{t+1}}[r_t+\gamma*V^{\pi}(\mathbf{x}_{t+1})]p(\mathbf{x}_{t+1}|\mathbf{x}_t)d\mathbf{x}_t]\ da_t$

$=\mathbb{E}_{a_t\sim\pi(a_t|\mathbf{x}_t)}[\mathbb{E}_{\mathbf{x}_{t+1}\sim p(\mathbf{x}_{t+1}|\mathbf{x}_t,a_t)}[r_t+\gamma*V^{\pi}(\mathbf{x}_{t+1})]]$

$=\mathbb{E}_{a_t\sim\pi(a_t|\mathbf{x}_t)}[r_t+\mathbb{E}_{\mathbf{x}_{t+1}\sim p(\mathbf{x}_{t+1}|\mathbf{x}_t,a_t)}[\gamma*V^{\pi}(\mathbf{x}_{t+1})]]$

위 식은 Bellman equation이라고 한다.