Diffusion은 신이고 GPT는 무적이다

Deterministic finite horizon problem

Continuous time에서의 deterministic finite horizon problem은 다음과 같다.

\[\begin{aligned} \textrm{minimize } \; & \int_0^T g(x(t), u(t)) dt + h(x(T)) \\ \textrm{subject to } \; & \dot{x} (t) = f(x(t), u(t)), \quad 0 \le t \le T \\ & x(0) = x_0 \end{aligned}\]

이 문제를 풀기 위해 다음과 같은 과정을 거친다.

  1. 시간 $0 \le t \le T$을 간격이 $dt$가 되게 $N$개로 discrete하게 나눈다
  2. Discrete time에서의 DP 알고리즘을 적용한다.
  3. 식을 적절히 변형한 뒤 $dt$를 0으로 보내 ($N$을 무한으로 보내) continuous time으로 만든다.

Discrete time에서의 deterministic finite horizon problem을 풀기 위한 DP 알고리즘은 다음과 같고,

\[\begin{aligned} J_N^\ast (x_N) &= h (x_N), \quad \quad \textrm{for all } x_N, \\ J_k^\ast (x_k) &= \min_{u_k \in U_k(x_k)} \bigg[ g_k (x_k, u_k) + J_{k+1}^\ast (f_k(x_k, u_k)) \bigg] \end{aligned}\]

continuous time에서의 표현으로 다시 쓰면 다음과 같다.

\[\begin{aligned} J_d^\ast (T, x) &= h(x), \quad \quad \textrm{for all } x, \\ J_d^\ast (t, x) &= \min_{u \in U} \bigg[ g (x, u) dt + J^\ast (t + dt, x + dx) \bigg] \end{aligned}\]


$(t, x)$ 주변에서 $J^\ast (t + dt, x + dx)$에 1차 테일러 전개를 하면 다음과 같다.

\[\begin{equation} J_d^\ast (t + dt, x + dx) = J_d^\ast (t, x) + \nabla_t J^\ast (t, x) + \nabla_x J^\ast (t, x)^T f(x, u) dt + o(dt) \end{equation}\]

$o(dt)$는 $\lim_{dt \rightarrow 0} o(t)/dt = 0$을 만족한다. DP 알고리즘의 $J_d^\ast (t, x)$ 식에 대입하면

\[\begin{aligned} J^\ast (t, x) &= \min_{u \in U} \bigg[ g (x, u) dt + J^\ast (t + dt, x + dx) \bigg] \\ &= \min_{u \in U} \bigg[ g (x, u) dt + J^\ast (t, x) + \nabla_t J^\ast (t, x) + \nabla_x J^\ast (t, x)^T f(x, u) dt + o(dt) \bigg] \\ \end{aligned}\]

이다. $J^\ast (t, x)$는 $u$에 무관하므로 양변에서 $J^\ast (t, x)$을 빼면

\[\begin{equation} 0 = \min_{u \in U} \bigg[ g (x, u) dt + \nabla_t J^\ast (t, x) dt + \nabla_x J^\ast (t, x)^T f(x, u) dt + o(dt) \bigg] \\ \end{equation}\]

이다. $dt \rightarrow 0$이면

\[\begin{equation} \lim_{dt \rightarrow 0} J_d^\ast (t, x) = J^\ast (t,x) \quad \textrm{for all } t, x \end{equation}\]

이다. 따라서 양변을 dt로 나누고 $dt \rightarrow 0$으로 극한을 취하면

\[\begin{equation} 0 = \min_{u \in U} \bigg[ g (x, u) + \nabla_t J^\ast (t, x) + \nabla_x J^\ast (t, x)^T f(x, u) \bigg] \\ \end{equation}\]

이다.


정리하면 $J^\ast (t,x)$에 대한 Hamilton–Jacobi–Bellman (HJB) equation이 된다.

\[\begin{equation} 0 = \min_{u \in U} \bigg[ g (x, u) + \nabla_t J^\ast (t,x) + \nabla_x J^\ast (t,x)^T f(x, u) \bigg], \quad \textrm{for all } t, x, \\ h(x) = J^\ast (T, x), \quad \textrm{for all } x \end{equation}\]

Stochastic finite horizon problem

Continuous time에서의 stochastic finite horizon problem은 다음과 같다.

\[\begin{aligned} \textrm{minimize } \; & \mathbb{E} \bigg[ \int_0^T g(x_t, u_t) dt + h(x_T) \bigg] \\ \textrm{subject to } \; & dx_t = f(x_t, u_t) dt + \sigma (x_t) dW_t, \quad 0 \le t \le T \\ & x |_{t=0} = x_0 \end{aligned}\]

$x + dx$의 1차 근사는

\[\begin{equation} x + dx = x + f(x, u) dt + \sigma (x) \epsilon (dt)^{1/2}, \quad \epsilon \sim \mathcal{N} (0, I) \end{equation}\]

이다. $(t, x)$ 주변에서 $J_d^\ast (t+dt, x+dx)$에 2차 테일러 전개를 하면 다음과 같다.

\[\begin{aligned} J_d^\ast (t+dt, x+dx) &= J_d^\ast (t+dt, x + f(x, u) dt + \sigma (x) \epsilon (dt)^{1/2}) \\ &= J_d^\ast (t, x) + \nabla_t J_d^\ast (t, x) dt + \nabla_x J_d^\ast (t, x)^T (f(x,u)dt + \sigma(x) \epsilon (dt)^{1/2}) \\ & \quad \quad + \frac{1}{2} \textrm{Tr} (\nabla_x^2 J_d^\ast (t, x) \cdot \sigma(x) \epsilon \epsilon^T \sigma(x)^T dt) + o((dt)^{3/2}) \end{aligned}\]

$\mathbb{E}[\epsilon] = 0$이고 $\mathbb{E} [\epsilon \epsilon^T] = I$임을 이용하여 양변의 기대값을 구하면 다음과 같다.

\[\begin{aligned} \mathbb{E}[J_d^\ast (t+dt, x+dx)] &= J_d^\ast (t, x) + \nabla_t J_d^\ast (t, x) dt + \nabla_x J_d^\ast (t, x)^T f(x,u)dt \\ & \quad \quad + \frac{1}{2} \textrm{Tr} (\nabla_x^2 J_d^\ast (t, x) \cdot \sigma(x) \sigma(x)^T dt) + o((dt)^{3/2}) \end{aligned}\]

위 식을 DP 알고리즘에 대입하여 정리하면 다음과 같다.

\[\begin{aligned} J_d^\ast (T, x) &= h(x), \quad \quad \textrm{for all } x, \\ J_d^\ast (t, x) &= \min_{u \in U} \mathbb{E} \bigg[ g (x, u) dt + J_d^\ast (t + dt, x + dx) \bigg] \\ &= \min_{u \in U} \bigg[ g (x, u) dt + \mathbb{E} [ J_d^\ast (t + dt, x + dx) ] \bigg] \\ &= \min_{u \in U} \bigg[ g (x, u) dt + J_d^\ast (t, x) + \nabla_t J_d^\ast (t, x) dt + \nabla_x J_d^\ast (t, x)^T f(x,u)dt \\ & \quad \quad \quad + \frac{1}{2} \textrm{Tr} (\nabla_x^2 J_d^\ast (t, x) \cdot \sigma(x) \sigma(x)^T dt) + o((dt)^{3/2}) \bigg] \end{aligned}\]

Deterministic problem과 마찬가지로 다음과 같이 위 식을 정리할 수 있다.

\[\begin{aligned} J_d^\ast (t, x) &= \min_{u \in U} \bigg[ g (x, u) dt + J_d^\ast (t, x) + \nabla_t J_d^\ast (t, x) dt + \nabla_x J_d^\ast (t, x)^T f(x,u)dt \\ & \quad \quad \quad + \frac{1}{2} \textrm{Tr} (\nabla_x^2 J_d^\ast (t, x) \cdot \sigma(x) \sigma(x)^T dt) + o((dt)^{3/2}) \bigg] \\ 0 &= \min_{u \in U} \bigg[ g (x, u) dt + \nabla_t J_d^\ast (t, x) dt + \nabla_x J_d^\ast (t, x)^T f(x,u)dt \\ & \quad \quad \quad + \frac{1}{2} \textrm{Tr} (\nabla_x^2 J_d^\ast (t, x) \cdot \sigma(x) \sigma(x)^T dt) + o((dt)^{3/2}) \bigg] \\ 0 &= \min_{u \in U} \bigg[ g (x, u) + \nabla_t J^\ast (t, x) + \nabla_x J^\ast (t, x)^T f(x,u) + \frac{1}{2} \textrm{Tr} (\nabla_x^2 J^\ast (t, x) \cdot \sigma(x) \sigma(x)^T) \bigg] \end{aligned}\]


정리하면 $J^\ast (t,x)$에 대한 Hamilton–Jacobi–Bellman (HJB) equation이 된다.

\[\begin{equation} - \nabla_t J^\ast (t, x) = \min_{u \in U} \bigg[ g (x, u) + \nabla_x J^\ast (t, x)^T f(x,u) + \frac{1}{2} \textrm{Tr} (\nabla_x^2 J^\ast (t, x) \cdot \sigma(x) \sigma(x)^T) \bigg], \quad \textrm{for all } t, x, \\ h(x) = J^\ast (T, x), \quad \textrm{for all } x \end{equation}\]

You may also enjoy