OPE(Offline Policy Evaluation)

 

 

본 포스팅은 Offline Policy Evaluation에 대해 정리한 글입니다. 아래의 내용을 참고하였습니다

Offline Policy Evaluation: Run fewer, better A/B tests

OPE 개요

우리는 비즈니스에서 목표(매출, 클릭율, 접속)를 개선하기 위해 의사결정을 하기 위해 A/B test에 많은 시간 및 자원을 소비하고 있습니다. 예를 들면 사용자의 클릭율 측면에서 어떤 UI가 좋은지 의사결정을 하기 위해 여러 안을 구성하고 접속한 사용자들에 대해 각 안을 랜덤으로 제시하는 실험을 수행합니다. 그리고 각 안에 노출된 집단별로 클릭율을 비교하여 가장 좋은 UI가 무엇인지 확인할 수 있죠.

사용자의 특성 및 외부 요인을 제거하여 공정하게 UI별로 클릭율을 비교할 수 있다는 측면에서 A/B test는 표준적이고 과학적인 방법입니다. 하지만, 그 과정에서 수반해야하는 비용이 분명히 존재합니다.

• 시간 투자 : 실험의 효과를 확인하기 위해 시간이 투자되며 매우 많은 실험을 하는 경우 더욱 많은 시간이 투자됩니다
• 나쁜 경험 제공 : 여러 안 중 다른 안에 비해 유저에게 좋지 않은 경험을 제공하는 안이 존재하기 마련입니다. 즉, 실험을 진행하며 나쁜 경험을 제공 받은 집단이 존재할 수 밖에 없습니다

이러한 문제점을 최소화하면서 A/B test를 진행할 수는 없을까요? 우리가 실제로 실험을 진행하기 전에 가장 효과적일 것으로 예측되는 안을 고를 수 있다면 해당 안에 대해서만 실제로 A/B test를 진행할 수 있을 것입니다. 즉, 모든 안에 대해 A/B test를 진행하는 것(AS-IS) 에 비해 시간을 덜 투자하고, 유저에게 나쁜 경험을 덜 제공하면서 실험을 진행할 수 있는 것이지요. 이것이 OPE가 도입된 이유입니다. A/B test를 수행하기 전에 좋을 것으로 예상되는 안을 필터링 해주는 역할을 수행하는 것이죠

• 과거 데이터를 활용하여 우리의 서비스가 변화하였을 때(새로운 정책을 적용하였을 때), 주요 지표가 어떻게 변할지 예측합니다
• 그리고 가장 효과가 좋을 것으로 예측되는 안 몇 개를 고릅니다
• 해당 안에 대해서 A/B test를 진행합니다

주요 용어 정리

우리는 "목표를 달성하기 위해 어떤 상황에서 어떤 행동을 해야하는가?"를 정하고자 합니다. 여기서 목표에 얼마나 근접한지 측정하기 위한 변수를 지표(metric)라고 합니다. 그리고 어떤 상황을 나타내는 것을 context라고 하고 해당 상황에서 우리가 취할 행동을 action이라고 합니다. 그리고 지표, 상황, 행동에 대한 기준을 정책(policy)라고 합니다. 위에서 설명한 하나하나의 "안"에 해당하는 것입니다

예를 들어 보겠습니다. 모바일 앱에서 유저의 접속을 유도하기 위해 푸시 알림을 보내는 의사결정을 하고 싶습니다. 조금 더 구체적으로 정의하면 "유저가 얼만큼 무접속인 상태일 때, 얼마만큼의 확률로 푸시 알림을 보내는 것이 유저 접속을 최대화 하는데 좋을까?" 입니다. 

• metric : 유저의 접속 여부
• context : 유저의 무접속 기간 & 무접속 기간에 따른 푸시 알림을 보낼 확률
• action : 푸시 알림을 보내는지 여부(보낸다 or 보내지 않는다)

언제 OPE가 효과를 발휘할 수 있는가?

정책이 매우 많은 경우

매우 많은 조합의 안이 존재하는 경우 OPE가 큰 효과를 발휘할 수 있습니다. 위에서 예를 든 모바일 앱 푸시 알림 문제를 생각해봅시다. 우리가 정해야 할 것은 무접속 기간 n일, 푸시를 보낼 확률 p 입니다. (실제로는 더 많은 parameter가 존재할 수 있습니다). 여기서 n과 p의 조합이 매우 많아질 수 있습니다. (n=1, p=0.9 / n=1, p=0.8 / n=2, p=0.9 / n=2, p=0.8....). 이를 모두 다 테스트하는 것은 너무 많은 시간이 소요될 것입니다. 이러한 경우에 우리는 과거 데이터(historical data)를 이용하여 효과가 좋을 것으로 예상되는 정책(n과 p)를 추리고, 해당 정책들에 대해서만 실제로 A/B test를 진행할 수 있습니다.

잘못된 정책으로 인한 리스크가 큰 도메인

잘못된 정책으로 인한 리스크가 매우 큰 도메인에서 OPE가 큰 효과를 발휘할 수 있습니다. 가령 유저에게 매우 나쁜 경험을 제공하여 유저의 이탈이 심각할 것으로 예상되는 도메인에서는 실험을 진행하기 전에 안전한 정책을 추리는 작업이 필수적이겠죠

 

OPE Method

IPS(Inverse Propensity Score), DM(Direct Method), DR(Doubly Robust Method)가 대표적인 OPE 방법입니다. 해당 방법들을 푸시 알림 정책 예시와 함께 설명하고자 합니다.

우리는 매일, 모든 유저에게 실행되는 푸시 알림 정책을 만들고 싶습니다. 그리고 과거에 아래의 정책으로 푸시 알림을 실행하여 모은 로그 데이터가 있습니다. (참고로 이러한 방법을 epsilon-greedy exploration 이라고 합니다) 

기존 정책으로 수집한 로그 데이터

• context
  • 유저가 앱에 접속한 이후 경과일(days_since_app_open)
  • 푸시를 보낼지 결정하는 파라미터(epsilon)
• action
  • 유저가 앱에 접속한지 경과 일자가 1일이 초과되지 않는 경우 (days_since_app_open <= 1), epsilon(0.9)의 확률로 푸시 알림을 보내지 않는다
  • 유저가 앱에 접속한 지 경과 일자가 1일이 초과되는 경우 (days_since_app_open > 1), epsilon(0.9)의 확률로 푸시 알림을 보낸다
• reward
  • 정책이 효과적인지 정량화하기 위해 우리는 각 context와 action에 대해 점수를 부여합니다.
    • 유저가 특정 날짜에 앱을 연 경우 10점, 그 이외는 0점
    • 특정 날짜에 앱을 열었으며, 해당 일자에 푸시 알림을 보낸 경우 3점 감점 (유저를 귀찮게 하였으므로)

IPS(Inverse Propensity Score)

우리가 새로운 정책을 정하고 이것이 기존 정책에 비해 좋은지 평가하기 위해서는 기존 정책과 새로운 정책 간의 분포 차이를 보정해주어야 합니다. 예를 들면 새로운 정책에서 days_since_app_open의 cutoff 를 5로 변경하였다고 합시다. 그러면 기존 대비 유저가 푸시 알림을 받을(action)을 확률이 낮아지게 됩니다. 이렇게 새로운 정책을 적용하였을 때 발생하게 되는 action의 불일치를 보정해주는 것입니다.

IPS(Inverse Propensity Score)

• $n$ : historical data의 샘플 수
• $x_k$ : context (여기서는 days_since_app_open와 epsilon)
• $a_k$ : action (여기서는 send or don't send)
• $r_k$ : (기존 정책 하에) context와 action이 주어졌을 때 reward
• $\hat{V}_{IPS}$ : (새로운 정책 하에) IPS를 사용하여 추론한 reward 기댓값
• $v(a_k|x_k)$ : (새로운 정책 하에) context가 주어졌을 때 action을 취할 확률
• $\hat{u}(a_k|x_k)$ : (기존 정책 하에) context가 주어졌을 때 action을 취할 확률

DM(Direct Method)

DM 은 IPS와 다른 방법을 사용합니다. IPS는 context가 주어졌을 때, action에 대한 확률을 불일치를 보정한다면 DM은 context와 action 정보를 이용하여 reward를 예측하는 모델을 만듭니다. 예측 모델을 기반으로 기존 정책과 새로운 정책의 reward를 비교하여 새로운 정책이 더 효과적인지 판단하는 것입니다 

DM (Direct Method)

• $\hat{V}_{DM}$ : (새로운 정책 하에) DM을 사용하여 추론한 reward 기댓값
• $v(a|x_k)$ : (새로운 정책 하에) context가 주어졌을 때 action을 취할 확률
• $\hat{r}(a_k, x_k)$ : context와 action이 주어졌을 때 주어졌을 때 reward 예측 값

DR(Doubly Robust)

DR은 위에서 소개드린 IPS와 DM 방법을 섞어놓은 방법입니다. 1) reward의 기댓값과 2) context하에 action이 주어질 확률에 대한 보정치를 동시에 활용합니다. 1과 2 중 하나라도 정확할 경우 정확한 추론이 가능하기 때문에 더 믿을 수 있는 추론을 할 수 있습니다. 1) 우선 context와 action 정보를 활용하여 reward 기댓값을 계산하고(DM), 2) 이에 대한 오차 부분을 action 분포 정보를 활용하여 보정합니다(IPS)

• $\hat{V}_{DR}$ : (새로운 정책 하에) DR을 사용하여 추론한 reward 기댓값
• $\hat{r}(x_k, v)$ : (새로운 정책 하에) DM을 사용하여 추론한 reward 예측값
• $v(a_k|x_k)$ : (새로운 정책 하에) context가 주어졌을 때 action을 취할 확률
• $\hat{u}(a_k|x_k)$ : (기존 정책 하에) context가 주어졌을 때 action을 취할 확률

마치며

효율적으로 A/B Test를 진행하기 위해 사전에 효과적일 것으로 예상되는 정책을 필터링하는 방법인 OPE에 대해 알아보았습니다

긴 글 읽어주셔셔 감사드리며 피드백은 언제나 환영입니다~

 

▼ 글이 도움이 되셨다면 아래 클릭 한번 부탁드립니다 :) ▼