Max-Policy Iteration, 재고(Revisited)

Max-policy iteration (최대 정책 반복)은 최대 연산자 (maximum operators)를 해결하고 수학적 최적화 (mathematical optimization)로 환원하는 연속적인 시도를 통해 정밀한 수치적 프로그램 불변량 (program invariants)을 계산하는 접근 방식입니다. 하지만 수학적 최적화는 비용이 많이 들 수 있습니다. 본 논문에서는 정수 (integers) 및 부동 소수점 수 (floating point numbers) 상의 방정식 시스템에 대한 max-policy iteration에 대하여, 수학적 최적화가 일반적인 가치 반복 (value iteration)으로 대체될 수 있음을 보여주며, 이는 여전히 종료가 보장됩니다. 응용 사례로서, widening operator (확장 연산자)를 완전히 배제하면서 정수 또는 부동 소수점 변수에 대한 정밀한 경계 분석 (bound analysis)을 얻을 수 있습니다. 또한 우리는 우변 (right-hand sides)이 미지수들의 아핀 결합 (affine combinations)의 최솟값들의 최댓값 (maxima of minima)인 유리수 (rational numbers) 상의 max-policy iteration에 대해서도 고찰합니다. 우리는 max-policy iteration에 의해 제기되는 최적화 문제를 해결하기 위한 선형 계획법 (linear programming)의 대안으로 min-policy iteration을 제안합니다. 우리는 max-min policy iteration이 유계 시스템 (bounded systems)에 대해 최소 해 (least solution)를 반환하는 것이 보장됨을 증명합니다. 또한 이 알고리즘을 무계 시스템 (unbounded systems)으로 확장하는 방법과, 계산된 결과의 건전성 (soundness) 및 최적성 (optimality)에 대한 인증서 (certificates)를 구성하는 방법을 보여줍니다.