🤖 machine learning

Quotient DAGs for Off-Policy Evaluation:Forward-Flow Importance Sampling and Exact Slate Propensities

본 논문은 자기회귀 추천 시스템에서 비효율적인 오프-정책 평가를 제거하고 순서가 없는 슬레이트 성향을 정확하게 계산하여 효율적인 오프-정책 평가를 가능하게 하기 위해 몫-DAG 프레임워크와 Forward-DP 알고리즘을 소개합니다.

원저자: Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

게시일 2026-05-29

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Ziwen Xie, Shaowen Xiang, Hongyu He, Dianbo Liu

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 새로운 요리법 (Target Policy) 이 얼마나 좋은지 판단하려는 셰프라고 상상해 보세요. 하지만 이 요리법을 직접 주방에서 조리해 볼 수는 없습니다. 비용이 너무 많이 들거나 위험하기 때문입니다. 대신, 다른 셰프 (Behavior Policy) 가 과거에 조리한 요리법들이 가득 적힌 노트를 가지고 있습니다. 당신의 목표는 오직 그 오래된 노트만을 사용하여 새로운 요리법이 얼마나 맛있는지 추정하는 것입니다. 이것이 오프-정책 평가 (Off-Policy Evaluation, OPE) 의 핵심 문제입니다.

문제: 잘못된 것을 세는 것

보통 새로운 요리법을 판단하기 위해, 당신은 그 이전 셰프가 취한 모든 단일 단계를 살펴봅니다. 당신은 "좋아, 소금을 넣고, 그 다음 후추를 넣고, 그 다음 마늘을 넣었군"이라고 말합니다. 그리고 그 정확한 순서에 기반하여 점수를 계산합니다.

하지만 여기에 함정이 있습니다. 때로는 재료를 넣는 순서가 최종 요리의 맛을 실제로 바꾸지 않기 때문입니다.

시나리오: 5 개의 노래 재생 목록이나 5 개의 전채 요리가 놓인 트레이와 같은 "슬레이트 (slate)"의 항목들을 상상해 보세요. 고객은 셰프가 그들을 놓은 순서가 아니라, 트레이 위에 어떤 5 개의 항목이 있는지에만 관심을 가집니다.
실수: 오래된 노트는 순서를 기록합니다 (노래 A, 그 다음 B, 그 다음 C...). 만약 당신이 그 특정 순서를 기반으로 점수를 계산한다면, 당신은 '순서'를 중요한 것으로 취급하는 것입니다. 하지만 고객이 그 순서에 관심이 없기 때문에, 당신은 계산에 "노이즈"를 추가하고 있는 것입니다.
결과: 이 노이즈는 엄청난 혼란 (분산) 을 만들어냅니다. 이는 여행 가방의 무게를 짐작하기 위해 가방 전체를 한 번에 저울에 올리는 대신, 안에 있는 각 양말을 하나씩 따로 저울에 올리는 것과 같습니다. 당신은 양말을 어떻게 세었는지에 따라 매우 다른 답변을 얻게 됩니다.

더 나아가, 순서를 무시한 특정 5 개 항목 그룹을 얻을 "진짜" 확률을 계산하는 것은 수학적인 악몽입니다. 5 개의 항목이 있다면, 그들이 선택될 수 있는 120 가지 다른 방법 (5 의 계승) 이 있습니다. 노트의 모든 단일 항목에 대해 이 수학을 수행하는 것은 대규모 그룹의 경우 계산상 불가능합니다.

해결책: "몫 DAG" (그룹화 지도)

저자들은 데이터를 바라보는 새로운 영리한 방법을 제안합니다. 셰프가 취한 모든 단일 경로를 보는 대신, 동일한 결과로 이어지는 모든 경로를 그룹화할 것을 제안합니다.

유사성: 재료를 넣는 서로 다른 순서를 나타내는 가지들이 있는 거대한 나무를 상상해 보세요.
- 옛 방법: 당신은 모든 가지를 하나씩 내려가서 무게를 재고, 그들을 평균내려 시도합니다.
- 새 방법 (몫 DAG): 동일한 세트의 재료로 끝나는 모든 가지들이 실제로 지도상의 동일한 "노드"임을 깨닫습니다. 당신은 그 모든 가지를 단일 점으로 축소합니다.
- 지도: 이는 방향성 비순환 그래프 (Directed Acyclic Graph, DAG) 를 생성합니다. 즉, 지금까지 선택된 항목의 순서가 아니라 선택된 항목의 세트에만 관심을 갖는 지도입니다.

마술 같은 트릭: 순방향 흐름 중요도 샘플링

이 단순화된 지도를 갖게 되면, 새로운 셰프가 특정 "세트"에 도달할 확률이 오래된 셰프에 비해 얼마나 되는지 알아야 합니다.

옛 방법: 답을 얻기 위해 120 가지 다른 순서의 확률을 모두 합산해야 했습니다.
새 방법 (순방향 DP): 저자들은 Forward-DP(동적 계획법) 라는 방법을 발명했습니다. 이를 단계별로 답을 구축하는 스마트한 계산기로 생각하세요.
- 빈 트레이 (확률 1) 로 시작합니다.
- "내가 1 개의 항목을 가지고 있다면, 2 번째 항목을 추가할 확률은 얼마인가?"라고 묻습니다.
- "내가 2 개의 항목을 가지고 있다면, 3 번째 항목을 추가할 확률은 얼마인가?"라고 묻습니다.
- 모든 120 가지 순서를 나열할 필요 없이 전체 세트의 확률을 계속 쌓아 올립니다.

이 방법은 정확합니다(추측하지 않습니다) 그리고 빠릅니다. 계산하는 데 몇 년이 걸리는 대신 (계승 시간), 관리 가능한 시간이 걸립니다 (트레이 크기에 지수적이지만 메뉴 크기에는 다항식입니다).

이것이 중요한 이유

덜 많은 노이즈: 관련 없는 "순서" 세부 사항을 무시함으로써 수학이 훨씬 더 깔끔해집니다. 추정치는 더 정확하고 안정적입니다.
실현 가능성: 이전에 정확하게 계산하기에는 너무 어려웠던 복잡한 추천 시스템 (예: "영화 10 편을 보여줘") 을 평가할 수 있게 합니다.
실제 세계 테스트: 저자들은 다음에서 이 방법을 테스트했습니다.
- 의료 데이터: 패혈증 (혈액 감염) 치료를 시뮬레이션했습니다. 그들의 방법은 이전 방법들보다 환자 결과에 대한 훨씬 더 정확한 예측을 제공했습니다.
- 추천 데이터: KuaiRec(비디오 추천) 이라는 데이터 세트를 사용했습니다. 그들은 그들의 방법이 비디오 그룹이 추천될 "진짜" 확률을 몇 초 만에 계산할 수 있음을 보였으며, 반면 옛 방식은 며칠이 걸리거나 불가능했을 것입니다.

요약

이 논문은 "어떻게"(행동의 순서) 를 과도하게 분석하는 것을 멈추고 "무엇"(최종 항목 세트) 에 집중하는 방법을 소개합니다. 동등한 경로들을 그룹화하고 스마트한 단계별 계산 방법 (Forward-DP) 을 사용함으로써, 그들은 새로운 전략을 훨씬 더 정확하고 효율적으로 평가할 수 있습니다. 특히 새로운 아이디어를 실제로 테스트하는 것이 너무 위험하거나 비용이 많이 드는 의료 및 추천 엔진과 같은 분야에서 그렇습니다.

기술적 요약: 오프폴리시 평가를 위한 몫 DAG

문제 제기

오프폴리시 평가 (OPE) 는 행동 정책 $\beta$ 로 수집된 데이터를 사용하여 목표 정책 $\pi$ 의 성능을 추정합니다. 표준 중요도 샘플링 (IS) 은 기록된 트래젝토리를 목표 정책과 행동 정책 간의 행동 확률 비율의 곱으로 재가중합니다. 그러나 이 접근법은 평가 대상이 무시하는 경우에도 생성 과정의 세부 사항을 의미 있는 것으로 취급하는 경향이 있습니다.

이 문제의 주요 사례는 슬레이트 추천에서 발생합니다. 현대의 생성기는 종종 슬레이트 (아이템 집합) 를 자기회귀적으로 구성하여 특정 순서대로 단계별 확률을 노출시킵니다. 그러나 보상과 하류 추정기는 종종 순서가 없는 슬레이트에만 의존합니다. 표준 트래젝토리 IS 는 특정 순서 경로의 가능도 비율을 할당하여 "공동 성향 격차 (joint-propensity gap)"를 생성합니다. 즉, 로거는 순서 확률을 노출하는 반면, 추정기는 순서가 없는 슬레이트의 전체 확률을 필요로 합니다. 이 정확한 순서가 없는 성향을 계산하려면 일반적으로 $K!$ 개의 모든 생성 순서에 대해 합산해야 하므로, 중간 크기의 슬레이트에서는 계산적으로 처리 불가능합니다. 또한, 순서를 중요하게 취급하면 보상이 생성 순서에 불변일 때 불필요한 분산 (nuisance variance) 이 발생합니다.

방법론

본 논문은 이러한 문제를 해결하기 위해 몫-DAG(Quotient-DAG) 관점을 도입합니다. 핵심 아이디어는 평가 대상에 충분한 동치 관계에 의해 히스토리 접두사의 롤아웃 트리를 몫 (quotient) 하는 것입니다.

몫 DAG 및 순방향 흐름:
- 롤아웃 트리는 평가 대상에 동등한 히스토리 접두사 (예: 순서와 상관없이 선택된 동일한 아이템 집합을 포함하는 접두사) 를 병합하여 축소됩니다.
- 이는 노드가 동치 클래스 (몫 상태) 를 나타내는 계층적 유방향 비순환 그래프 (DAG) 를 형성합니다.
- 단일 실현 경로의 비율로 가중치를 부여하는 대신, 이 방법은 순방향 흐름 비율 (forward-flow ratio) $F_\pi(z)/F_\beta(z)$ 를 사용하여 가중치를 할당합니다. 여기서 $F_\mu(z)$ 는 정책 $\mu$ 하에서 노드 $z$ 에 도달하는 확률 질량입니다.
- 이 접근법은 기존 방법들을 일반화합니다: 결정별 IS, 주변화 IS, 그리고 알려진 추상화 MIS 는 서로 다른 동치 관계 선택에 해당하는 특수한 경우입니다.
순방향 흐름 중요도 샘플링 (FF-IS):
- 일반적인 유한 시간 OPE 에 대해, 추정기는 결정별 IS(PDIS) 의 샘플링된 접두사 비율을 몫 가능도 비율로 대체합니다.
- 이론적 분석에 따르면, 터미널 몫 측정 가능 반환 (terminal quotient-measurable returns) 의 경우, 이 가중치는 "클래스 내" 목표 - 행동 불일치를 제거하여 불필요한 분산 감소를 정량화하는 정확한 분산 격차 식을 제공합니다.
슬레이트 OPE 를 위한 순방향 DP:
- 본 논문은 집합 충분 (set-sufficient) 인터페이스 (정의 1) 하의 자기회귀 슬레이트 생성에 이 프레임워크를 특화시킵니다. 정책이 다음 아이템 선택 확률이 컨텍스트와 이미 선택된 아이템 집합에만 의존하고 순서에는 의존하지 않을 때, 해당 정책은 집합 충분합니다.
- 집합 충분성 하에서, 순열 몫은 부분집합 DAG에 해당하며, 여기서 노드는 카탈로그의 부분집합이고 간선은 선택되지 않은 아이템을 추가합니다.
- 순방향 DP 알고리즘: 동적 프로그래밍 알고리즘은 순열이 아닌 부분집합에 대해 합산함으로써 정확한 순서가 없는 슬레이트 성향 $F_\mu(S|x)$ $F_{μ} (S ∣ x)$ 를 계산합니다.
  - 복잡도: $O((M + K) \cdot 2^K)$ 이며, 여기서 $M$ 은 카탈로그 크기이고 $K$ 는 슬레이트 크기입니다. 이는 $K!$ 나열을 피합니다.
  - 최적성: 본 논문은 집합 충분 정책의 정확한 순서가 없는 성향을 계산하는 모든 결정적 알고리즘이 최악의 경우 슬레이트의 모든 고유 부분집합을 쿼리해야 함을 증명하여, 상수 인자까지 Forward-DP 가 쿼리 최적임을 입증합니다.

주요 기여

이론적 프레임워크: 더 거친 표본 공간에서의 순방향 흐름 비율로서 정확한 가능도 비율을 유도하는 OPE 를 위한 통합된 몫-DAG 관점.
알고리즘적 혁신: 컨텍스트 의존적, 집합 충분 자기회귀 로거에 대한 정확한 순서가 없는 슬레이트 성향을 카탈로그 크기에 다항식이고 슬레이트 크기에 지수적으로 (K 에 고정 매개변수 처리 가능) 계산하는 Forward-DP 알고리즘.
분산 감소: 보상이 슬레이트의 생성 시퀀스에 불변일 때 특히, 관련 없는 생성 순서 (슬레이트 추천에서의 생성 순서) 와 관련된 분산 성분 (순서 - 불필요 분산) 을 몫 가중치가 제거한다는 공식적 증명.
슬레이트 OPE 를 위한 원시 도구: 고정 점수 Plackett-Luce 공식이 적용되지 않는 컨텍스트 의존적 로거에 대한 정확한 성향 기반 평가 및 모델 선택을 가능하게 하는 Forward-DP 의 도입.

실험 결과

저자들은 유한 시간 MDP 벤치마크 및 슬레이트 추천 작업에서 이 방법을 평가했습니다:

유한 시간 MDP(패혈증 및 ICU-패혈증):
- 순방향 흐름 IS(FF-IS) 는 표준 트래젝토리 IS 및 기타 베이스라인 (예: DualDice, GenDICE) 에 비해 Root Mean Square Error(RMSE) 를 크게 감소시켰습니다.
- 패혈증 벤치마크에서 FF-WIS 는 RMSE 를 0.291(WIS) 에서 0.0568 로 감소시켰습니다.
- 이러한 개선은 전이 모델을 적합시키지 않고 기록된 트래젝토리만 사용하여 달성되었습니다.
KuaiRec 슬레이트 실험:
- 계산 효율성: Forward-DP 는 $K!$ 나열보다 수 배에서 수 천 배 빠른 속도로 정확한 성향을 계산합니다. $K=8$ 의 경우, 나열은 약 97,108 초가 소요된 반면 Forward-DP 는 약 8.94 초가 소요되었습니다. $K=12$ 의 경우 나열은 불가능하지만 Forward-DP 는 약 13.7 초에 완료됩니다.
- 하류 OPE: Forward-DP 가중치를 사용한 추정기 (FF-OIS, FF-DR) 는 모든 슬레이트 크기 ( $K \in \{4, 6, 8\}$ ) 에서 RMSE 측면에서 트래젝토리 가중치 대응물 (OIS, DR) 보다 일관되게 우수한 성능을 발휘했습니다.
- 모델 선택: 자기회귀 트랜스포머 추천기 간의 오프폴리시 모델 선택에서 Forward-DP 를 활용한 추정기 (예: Tree-DR, DP-OPCB-DR) 는 트래젝토리 기반 방법에 비해 우수한 Top-1 정확도, 스피어만 상관관계 및 더 낮은 후회도를 달성했습니다.

중요성 및 주장

본 논문은 제안된 프레임워크가 결정별 IS 에 대한 Rao-Blackwellization을 제공한다고 주장합니다. 충분한 동치 관계 하에서 롤아웃 트리를 몫함으로써, 이 방법은 생성 순서와 같은 히스토리 세부 사항과 관련된 불필요한 분산을 제거합니다.

특히 슬레이트 추천의 경우, 본 논문은 Forward-DP 가 컨텍스트 의존적 자기회귀 로거를 위한 누락된 OPE 원시 도구를 제공한다고 주장합니다. 부분 슬레이트에 따라 아이템 점수가 변하지 않는 고정 점수 가정이나 몬테카를로 근사에 의존하는 이전 방법들과 달리, Forward-DP 는 다음 아이템 소프트맥스가 부분 슬레이트에 의존하는 경우를 처리하며, 계승 나열 없이 정확한 공동 성향을 계산합니다. 이는 현대의 트랜스포머 기반 추천기에 대한 실용적이고 정확한 성향 기반 평가 및 모델 선택을 가능하게 합니다.

저자들은 한계점을 언급했는데, 여기에는 배포 시 선택된 집합을 표준화 (canonicalizing) 해야 할 수 있는 집합 충분 가정의 필요성과 슬레이트 크기 $K$ 에 따른 지수적 확장이 포함됩니다. 그러나 그들은 $K!$ 가 처리 불가능한 일반적인 슬레이트 크기 ( $K \le 10$ ) 에서는 이것이 실용적이라고 주장합니다.