Kleene’s Fixpoint Theorem

Policy Iteration

연관성

정책 공간 $\{ π_i \}_i$를 Π라 하자. Policy Iteration 반복 한 번의 연산을 함수 T : Π → Π라 하자.

조건1. D가 CPO ↔ Π가 CPO

1. Π는 poset: $\pi \sqsubseteq \pi' := \forall s.\ v^{\pi}(s)\le v^{\pi'}(s)$로 partial order가 정의된다. (일부 state에서만 다른 정책보다 값이 클 수 있으므로, total order는 아니다.)
2. Π는 CPO: Π는 $|A|^{|S|}$ 크기의 유한 집합이므로, 모든 chain은 길이가 유한하며, chain의 끝이 lub이다. 그러므로 모든 chain의 lub는 Π 안에 존재한다.

조건2. f가 연속 함수 ↔ T가 연속 함수

1. T가 monotone: $\pi_{i+1} = T(\pi_i)$라 할 때, $v^{\pi_i}(s) \leq \max_a{Q^{\pi_i}(s, a)} \leq v^{\pi_{i+1}}(s) \iff \pi_i \sqsubseteq \pi_{i+1}$

2. T가 continuous: 정의역이 유한 집합인 monotone 함수 T는 continuous하다.

   

결과1. 고정점 계산 방법

policy iteration에서는 정적 분석과 달리, “최소” 고정점을 찾을 필요가 없다. 적어도 T가 monotonic하다는 것만 보장되어도 사실 충분하다. 고정점 계산의 관점에서 임의로 선택한 초기 정책이 최적 정책과 비교해 어디 있는지에 따라 계산 양상이 달라진다.

• 초기 정책 ⊑ 최적 정책: T 적용 반복을 통해 고정점인 최적에 도달하는 게 보장된다. (by 고정점 정리)
• 초기 정책 ⊒ 최적 정책: 최적 정책은 최대성으로 인해 유일하다. 따라서 초기 정책 = 최적 정책가 성립하고 반복을 즉시 종료한다.