Published on

Bellman Operator

Bellman Operator

Bellman Equation to Bellman Operator

Expected Bellman Equation

Expected Bellman Equation은 다음과 같다.

vπ(s)=Σa∈Aπ(a∣s)(Rsa+γΣs′∈S)Pss′avπ(s′)v_\pi(s) = \Sigma_{a \in A} \pi (a|s) (R_s^a + \gamma \Sigma_{s' \in S}) P_{ss'}^a v_\pi(s')

이때 어떤 policy π\pi를 가정하면 다음과 같이 표현할 수 있다.

Pss′π=Σa∈Aπ(a∣s)Pss′aP_{ss'}^\pi = \Sigma_{a \in A} \pi(a|s) P_{ss'}^a Rsπ=Σa∈Aπ(a∣s)RsaR_s^\pi = \Sigma_{a \in A} \pi (a|s) R_s^a

즉 policy π\pi를 따를 때 state ss에서 s′s'로 변화할 확률은 Pss′πP_{ss'}^\pi이고, state ss에서 받을 것으로 예상되는 reward는 RsπR_s^\pi라는 것이다.

Bellman Operator

Bellman Operator는 기본적으로 위와 같은 Bellman equation과 내용적으로는 동일하지만 수학적으로 보다 편리하게 사용하기 위해 Operator의 형태로 표현한 것이라고 할 수 있다.

우선 어떤 state space SS의 state 개수가 nn개라고 하자. 그럼 위의 식을 다음과 같이 벡터 간의 연산으로 표현할 수 있다.

[vπ(s1)⋮vπ(sn)]=[R1π⋮Rnπ]+γ[P11π⋯P1nπ⋮⋱⋮Pn1π⋯Pnnπ][vπ(s1)⋮vπ(sn)]\begin{bmatrix} v_\pi(s_1) \\ \vdots \\ v_\pi(s_n) \end{bmatrix} = \begin{bmatrix} R_1^\pi \\ \vdots \\ R_n^\pi \end{bmatrix} + \gamma \begin{bmatrix} P_{11}^\pi & \cdots & P_{1n}^\pi \\ \vdots & \ddots & \vdots \\ P_{n1}^\pi & \cdots & P_{nn}^\pi \end{bmatrix} \begin{bmatrix} v_\pi(s_1) \\ \vdots \\ v_\pi(s_n) \end{bmatrix}

이를 좌변과 우변이 모두 n * 1 백터인 백터 연산으로 표현 가능한데,

vπ=Rπ+γPπvπv_\pi = R^\pi + \gamma P^\pi v_\pi

이를 bellman operator라고 하고 기호 τ\tau를 이용해 표현한다. 구체적으로 expected bellman operator와 bellman optimality operator는 다음과 같이 정의된다.

τπ(v)=Rπ+γPπvπτ∗(v)=max⁡a∈A(Ra+γPav)\tau^\pi (v) = R^\pi + \gamma P^\pi v_\pi\\ \tau^*(v) = \max_{a \in A} (R^a + \gamma P^a v)

Bellman operator는 수학적으로 I ⁣Rn→I ⁣Rn\rm I\!R^n \rightarrow \rm I\!R^n로, 다시 말해 I ⁣Rn\rm I\!R^n 공간의 어떤 한 점에서 다른 한 점으로 매핑한다는 의미를 가진다. 이와 같은 특성을 이용하면 operator theory의 unique fixed point 개념을 적용하여 모델의 수렴성 여부를 판단할 수 있다.

Usage of Bellman Operator

Contraction of Bellman operator

어떤 Bellman operator가 수축(contraction)한다는 것은 다음이 성립한다는 것을 의미한다.

for any policy π any initial vector v,lim⁡k→∞(τπ)k=vπ, lim⁡k→∞(τ∗)k=v∗where vπ is the value of policy πand v∗ is the value of an optimal policy π∗\text{for any policy} \ \pi \ \text{any initial vector} \ v, \\ \lim_{k \rightarrow \infty}(\tau^\pi)^k = v_\pi, \ \lim_{k \rightarrow \infty}(\tau^*)^k = v_* \\ \text{where} \ v_\pi \ \text{is the value of policy} \ \pi \\ \text{and} \ v_* \ \text{is the value of an optimal policy} \ \pi_*

즉, 수축한다는 것은 어떤 v vector에서 어떤 policy를 가지고 시작하더라도 무한히 반복하면 해당 policy의 vπv_\pi로 수렴하게 된다는 것을 의미한다.

이 내용은 contraction mapping theory를 통해 증명이 되며, 구체적으로는 wiki의 Banach fixed point theorem을 참조하면 좋을 것 같다.

Reference