최근에 budget pacing 알고리즘을 정리한 아래 논문을 읽고 있다.
https://arxiv.org/abs/2503.06942
이 논문의 bidding problem formulation 챕터를 보면 max delivery 문제를 세운 다음 primal-dual method로 최적 입찰가를 유도한다. 그런데 유도 과정에서 갑자기 min max가 나오고, 또 갑자기 KKT condition이 나오는데 왜 이런 것들이 필요한지 한번에 이해가 되지 않았다. 최적화 수업에서 배웠던 내용인데도 광고 도메인 문제에 적용된 형태로 보니 낯설었다. 유도 과정을 한 단계씩 다시 따라가면서 정리하고자 한다. 이 글에서는 second price auction 상황만 다룬다.
Max delivery 문제는 예산 제약이 걸린 knapsack 문제다.
우선 문제 정의부터 살펴보자. max delivery는 광고주가 예산을 정해두고 그 안에서 최대한 많은 클릭을 받고 싶어하는 상황이다.
\[ \max_{x_t \in \{0,1\}} \sum_{t=1}^{T} x_t r_t, \quad s.t. \sum_{t=1}^{T} x_t c_t \leq B \]
여기서 T는 하루 동안 들어올 것으로 예측되는 auction opportunity의 개수를, $r_t$는 t번째 경매의 predicted CTR을, $c_t$는 t번째 경매에서 나를 제외한 나머지 입찰자들의 최고 eCPM을, B는 하루 예산을 의미한다. $x_t$는 t번째 경매를 이겼는지 여부를 나타내는 binary 변수이다.
여기서 $c_t$의 정의를 명확히 해둘 필요가 있다. second price auction이므로 내가 이겼을 때 지불하는 금액이 곧 $c_t$이다. 다만 $c_t$는 내가 이기든 지든 상관없이 정의되는 값이고, 내가 이겼을 때만 청구된다. 그래서 지출액을 $x_t c_t$로 쓸 수 있는 것이다. 엄밀하게는 이 경매의 second price라기보다 내 입장에서의 threshold price에 가깝다. 내가 졌다면 second price는 내 입찰가일 수도, 다른 입찰자의 값일 수도 있기 때문이다.
내가 입찰가 $b_t$를 낼 때 승패는 아래와 같이 결정된다.
\[ x_t = 1\{b_t > c_t\} \]
여기서 한 가지 짚고 갈 점이 있다. 우리가 실제로 컨트롤하는 변수는 $x_t$가 아니라 $b_t$이다. $x_t$는 내 입찰과 경쟁 상황이 만들어낸 결과일 뿐이다. 그런데 목적함수와 제약식이 이겼는지 여부만으로 깔끔하게 표현되기 때문에 $x_t$를 마치 결정 변수인 것처럼 모델링한 것이다. 그래서 나중에 $x_t$에 대한 규칙을 다시 $b_t$로 번역하는 단계가 반드시 필요하다.
이 문제를 왜 직접 풀 수 없을까? 흔히 knapsack 문제라서 NP-hard이기 때문이라고 생각하기 쉬운데, 필자가 다시 생각해보니 그게 본질적인 이유는 아닌 것 같다. $x_t \in [0,1]$로 완화하면 $r_t / c_t$ 내림차순으로 greedy하게 담기만 하면 정확한 해가 나오기 때문이다. 진짜 문제는 정렬을 하려면 T개의 경매를 전부 손에 쥐고 있어야 한다는 점이다. t=1 시점에 나머지 경매는 존재하지도 않는다. 게다가 $c_t$는 입찰 전에 알 수도 없다. 설령 신이 최적해 $(x_1, \cdots, x_T)$를 알려준다 해도 그건 어제 지나간 특정 경매 시퀀스에 대한 정답표이지 오늘 들어오는 요청에 쓸 수 있는 정책이 아니다.
primal 문제는 max min, dual 문제는 min max 형태이다.
이제 Lagrangian을 세워보자.
\[ L(x, \lambda) = \sum_{t=1}^{T} x_t r_t - \lambda \left( \sum_{t=1}^{T} x_t c_t - B \right), \quad \lambda \geq 0 \]
여기서 $\lambda$는 예산 제약에 붙은 Lagrange multiplier, 즉 dual variable이다. 제약을 어기면 괄호 안이 양수가 되어 목적함수에서 그만큼 깎인다. 예산 1원당 $\lambda$만큼의 벌금을 매겨서 제약 있는 문제를 제약 없는 문제로 바꾼 것이다.
논문에서는 이 Lagrangian을 세운 다음 바로 아래처럼 dual을 쓴다.
\[ \min_{\lambda \geq 0} L^{*}(\lambda) = \min_{\lambda \geq 0} \max_{x_t \in \{0,1\}} L(x, \lambda) \]
필자는 여기서 min max가 왜 갑자기 나오는지 이해가 되지 않았다. Lagrangian을 세운 것까지는 알겠는데 최대화 문제를 풀고 있었으면서 왜 바깥에 min이 붙는가 하는 의문이었다. 그런데 primal 문제도 Lagrangian으로 쓸 수 있다는 것을 생각해보면 답이 나온다. $g(x) = \sum_t x_t c_t - B$라 두고 x를 고정한 채 $\lambda$에 대해 최소화해보자. x가 고정이면 $f(x)$와 $g(x)$는 그냥 숫자이므로 $f - \lambda g$는 $\lambda$에 대한 일차함수다. $g(x) > 0$이면 $-\lambda g(x)$가 음수이므로 $\lambda$를 키울수록 값이 작아지고, 최소값을 찾는 입장에서는 $\lambda$를 무한대로 보내게 되어 $-\infty$가 된다. 반대로 $g(x) \leq 0$이면 $\lambda$를 키울수록 값이 커지므로 최소값은 $\lambda = 0$에서 $f(x)$가 된다.
\[ \min_{\lambda \geq 0} L(x, \lambda) = f(x) \ (g(x) \leq 0), \quad -\infty \ (g(x) > 0) \]
즉, $\lambda$에 대한 최소화가 제약 조건을 그대로 재현해버린 것이다. 위반한 x는 $-\infty$가 되어 바깥에서 x로 최대화할 때 알아서 탈락한다. 따라서 아래가 성립한다.
\[ f^{*} = \max_{x} \min_{\lambda \geq 0} L(x, \lambda), \quad q^{*} = \min_{\lambda \geq 0} \max_{x} L(x, \lambda) \]
여기서 중요한 점은 앞의 식이 정리가 아니라 항등식이라는 것이다. 증명할 것이 없다. $\min_{\lambda}$가 제약 조건을 흉내내도록 설계됐을 뿐이다. 즉, dual은 min max라는 새로운 형태를 도입한 게 아니라 primal의 max min에서 순서만 뒤집은 것이다. 논문이 primal을 Lagrangian 형태로 써주지 않아서 이 대칭이 보이지 않았던 것뿐이다.
그렇다면 순서를 뒤집어도 값이 같을까? 일반적으로는 아니다. 임의의 $\bar{x}, \bar{\lambda}$에 대해 $\min_{\lambda} L(\bar{x}, \lambda) \leq L(\bar{x}, \bar{\lambda}) \leq \max_{x} L(x, \bar{\lambda})$가 성립하고, 이게 모든 $\bar{x}, \bar{\lambda}$에 대해 성립하므로 왼쪽을 최대화하고 오른쪽을 최소화해도 부등호가 유지된다.
\[ \max_{x} \min_{\lambda \geq 0} L \leq \min_{\lambda \geq 0} \max_{x} L \]
직관적으로는 나중에 움직이는 쪽이 유리하다고 이해하면 된다. max min은 x를 먼저 공개하고 $\lambda$가 그걸 보고 후려치는 게임이라 값이 낮게 눌리고, min max는 반대라 값이 높다. 등호가 성립하려면 strong duality가 필요한데 $x_t \in \{0,1\}$은 convex set이 아니므로 우리 문제에서는 보장되지 않는다. 이 부분은 뒤에서 다시 언급하겠다.
dual space에서는 문제가 경매 하나 단위로 분해된다.
그렇다면 왜 굳이 순서를 뒤집는 것일까? Lagrangian을 정리해보면 답이 보인다.
\[ L(x, \lambda) = \sum_{t=1}^{T} x_t (r_t - \lambda c_t) + \lambda B \]
분배법칙으로 같은 t끼리 묶은 것뿐이고 $\lambda B$는 x와 무관한 상수다. 여기서 $\lambda$를 고정된 상수로 보면 각 항 $x_t (r_t - \lambda c_t)$가 서로 완전히 독립이다. primal에서는 제약식이 모든 t를 묶어버려서 $x_5$를 결정하려면 $x_{100}$을 알아야 했는데, Lagrangian에서는 제약식이 사라지고 예산이 $\lambda$라는 단가로만 반영되기 때문이다. 즉, 각 항을 따로 최대화한 것들의 합이 전체 최대값이 된다.
$x_t$가 0 또는 1이므로 각 항의 최대화는 자명하다. $r_t - \lambda c_t > 0$이면 1, 아니면 0이다. 여기서 $r_t - \lambda c_t$는 이 임프레션의 순가치로 읽으면 된다. $r_t$는 얻는 클릭이고 $\lambda c_t$는 그 비용을 $\lambda$라는 환율로 클릭 단위로 환산한 값이니, 남는 게 있으면 사라는 것이다. 이를 대입하면 dual function이 나온다.
\[ L^{*}(\lambda) = \sum_{t=1}^{T} (r_t - \lambda c_t)_{+} + \lambda B \]
여기서 $(z)_{+} = 1\{z > 0\} \cdot z$는 ReLU function이다. T차원 조합 문제가 스칼라 $\lambda$ 하나에 대한 1차원 convex 최소화 문제로 바뀌었다. 순서를 뒤집는 이유가 이것이다.
최적 입찰가는 경매 메커니즘과의 대조로 얻어진다.
이제 안쪽 최대화가 준 규칙을 다시 정리해보자. $\lambda^{*} > 0$이므로 부등호 방향을 유지한 채 양변을 나눌 수 있다.
\[ x_t = 1 \iff r_t - \lambda^{*} c_t > 0 \iff \dfrac{r_t}{\lambda^{*}} > c_t \]
문제는 $c_t$를 모른다는 점이다. 이 부등식을 직접 계산할 수가 없다. 그런데 앞에서 정의한 경매 규칙을 다시 보자.
\[ x_t = 1 \iff b_t > c_t \]
두 식을 나란히 놓고 비교해보면, 우리가 원하는 승패 패턴과 실제로 일어나는 승패 패턴이 모든 $c_t$에 대해 일치하려면 아래여야 한다.
\[ b_t^{*} = \dfrac{r_t}{\lambda^{*}} \]
즉, $c_t$를 몰라도 최적 규칙이 그대로 실행된다. 경매 메커니즘이 비교를 대신 해주기 때문이다. 이 유도가 어떤 함수를 미분해서 얻은 게 아니라 최적해를 구현하는 입찰가를 역산한 것이라는 점이 개인적으로 인상적이었다. 물론 이 논증은 $x_t$가 $b_t$의 임계값 함수라는 데 의존한다. first price auction이었다면 지불액이 $b_t$ 자신이 되므로 이 대조가 그대로 통하지 않는다.
bid per click은 여기서 단위 변환으로 나온다. $b_t^{*}$는 임프레션 1회에 대한 입찰가인데, 실무 시스템은 보통 클릭당 단가를 파라미터로 받고 거기에 pCTR을 곱해서 eCPM을 만든다. 그 형태로 분해해보자.
\[ b_t^{*} = \dfrac{r_t}{\lambda^{*}} = r_t \times \dfrac{1}{\lambda^{*}} \]
$r_t$는 임프레션당 클릭 수이고 $b_t^{*}$는 임프레션당 원이므로 $1 / \lambda^{*}$는 클릭당 원이 된다. 따라서 아래와 같다.
\[ b_{click}^{*} = \dfrac{1}{\lambda^{*}} \]
즉, $b_{click}^{*}$는 새로 유도한 게 아니라 $b_t^{*}$를 $r_t$와 상수의 곱으로 인수분해했을 때의 그 상수다. 여기서 중요한 점은 이 값이 t에 의존하지 않는다는 것이다. 임프레션마다 달라지는 건 $r_t$뿐이고 정책 자체는 스칼라 하나다. pCTR 모델 팀과 pacing controller가 깔끔하게 분리되는 근거가 여기에 있다.
complementary slackness가 $\lambda^{*}$을 관측 가능한 조건으로 바꿔준다.
논문은 이 시점에 갑자기 KKT condition을 꺼낸다. 필자는 처음에 이게 왜 여기서 나오는지 몰랐다. 최적 입찰가는 이미 유도됐는데 무슨 조건이 더 필요한가 싶었다.
우선 KKT condition이 뭔지부터 정리해보자. 부등식 제약이 있는 최적화 문제의 최적해가 만족해야 하는 네 가지 조건이다. primal feasibility는 $g(x^{*}) \leq 0$, dual feasibility는 $\lambda^{*} \geq 0$, stationarity는 $\nabla_x L(x^{*}, \lambda^{*}) = 0$, complementary slackness는 $\lambda^{*} g(x^{*}) = 0$이다. Lagrange가 등식 제약에 대해 만든 조건을 부등식 제약으로 확장한 것이고, 부등식이 되면서 승수의 부호 조건과 제약이 활성인지를 구분하는 조건이 새로 필요해진 것이다.
이 중에서 앞에서 이미 쓴 것이 stationarity다. 안쪽 최대화로 $x_t$의 규칙을 얻은 게 그것이고, 우리 문제는 x가 이산이라 미분 대신 부호 판정으로 대체됐을 뿐이다. 그렇다면 논문이 여기서 꺼내는 건 뭘까? complementary slackness 하나다.
\[ \lambda^{*} \left( \sum_{t=1}^{T} x_t c_t - B \right) = 0 \]
곱이 0이려면 둘 중 하나는 0이어야 한다. 따라서 $\lambda^{*} > 0$이라고 가정하면 나머지가 0이어야 한다.
\[ \sum_{t=1}^{T} x_t c_t = B \]
부등식 $\leq B$가 등식 $= B$로 격상됐다. 이게 왜 중요할까? $\lambda^{*}$의 원래 정의는 $\arg\min_{\lambda \geq 0} L^{*}(\lambda)$인데 이건 $r_t$와 $c_t$ 전체를 알아야 계산할 수 있는 값이라 실서빙에서는 쓸 수가 없다. 그런데 complementary slackness는 $\lambda^{*}$를 전혀 다른 방식으로 특징짓는다. 예산을 정확히 소진시키는 값이라는 것이다. 이 서술은 미래를 몰라도 확인할 수 있다. 지금까지 얼마 썼는지만 보면 되기 때문이다.
즉, KKT가 최적성 조건을 관측 가능한 신호로 번역해준 것이다. 이게 pacing controller가 존재할 수 있는 근거가 된다. dual function을 미분해보면 이 점이 더 분명해진다.
\[ \dfrac{d L^{*}}{d\lambda} = B - \sum_{t=1}^{T} x_t(\lambda) c_t \]
gradient가 정확히 예산 오차다. 지출이 B보다 크면 gradient가 음수이므로 $\lambda$를 키우는 게 감소 방향이고, 이는 입찰가를 낮추는 것에 해당한다. 반대면 반대다. dual 문제의 최적성 조건인 gradient가 0인 지점과 complementary slackness가 정확히 같은 식이라는 점이 재미있다. 우연이 아니라 같은 사실의 두 표현이다.
그런데 이 KKT condition은 왜 성립하는 걸까? 가정하고 들어가는 것인지 궁금했는데, 정리해보니 complementary slackness는 strong duality의 직접적인 귀결이다. $f^{*} = q^{*} = L^{*}(\lambda^{*}) = \max_x [f(x) - \lambda^{*} g(x)] \geq f(x^{*}) - \lambda^{*} g(x^{*})$인데 $f(x^{*}) = f^{*}$이므로 $\lambda^{*} g(x^{*}) \geq 0$이 나온다. 한편 $\lambda^{*} \geq 0$이고 $g(x^{*}) \leq 0$이므로 $\lambda^{*} g(x^{*}) \leq 0$이다. 양쪽에서 조이면 0이 된다.
문제는 그 strong duality가 우리 문제에서 보장되지 않는다는 점이다. $x_t \in \{0,1\}$이 convex set이 아니기 때문이다. 그러니 엄밀하게는 KKT가 정확히 성립한다는 보장이 없고 integrality gap이 존재한다. 논문도 이걸 알고 있어서 duality gap을 다루는 절을 따로 두고 있다. 다만 제약이 하나뿐인 knapsack의 LP 해에서 분수값을 갖는 $x_t$는 최대 하나이므로 gap이 최대 임프레션 하나 분량이고, T가 수십억이면 상대적으로 무시할 만하다는 논리로 넘어간다. 그리고 생각해보면 실제 서빙에서는 $b_t = r_t / \lambda$로 입찰했을 때 낙찰이 확률적으로 일어나므로 실효 $x_t$가 0과 1 사이의 값이 된다. 물리적으로는 이미 LP relaxation을 구현하고 있는 셈이라, 이산성은 유도 편의를 위한 서술이었던 게 아닌가 하는 생각이 들었다.
$\lambda^{*}$는 예산의 shadow price이다.
마지막으로 $\lambda^{*}$가 무엇인지 정리해보자. 하나의 값에 여러 얼굴이 있다.
정의대로 보면 dual 문제의 최적해다. 하지만 앞에서 언급했듯 이건 계산할 수 없는 서술이다. 논문도 사실 $\lambda^{*}$를 구하지 않는다. feasible하다고 가정하고 최적해가 존재한다고 하고 이름만 붙일 뿐이다. 실제로 이 값을 어떻게 추정할 것인가가 논문의 나머지 200페이지 전부이고, PID, dual online gradient descent, MPC, LQG가 전부 그 방법론들이다. 처음 읽을 때 이 부분에서 유도가 끝나지 않은 것 같아 답답했는데, 이 절은 목표가 무엇인지를 정의하는 절이고 도달 방법은 뒤에 있다고 생각하니 정리가 됐다.
경제적으로 보면 $\lambda^{*}$는 예산의 shadow price다. 예산 1원을 더 주면 클릭이 몇 개 늘어나는가를 나타내므로 단위가 클릭당 원의 역수, 즉 원당 클릭이다. 그래서 역수인 $1 / \lambda^{*}$가 원당 클릭의 역수가 되어 클릭당 원, 즉 클릭당 지불 의사 가격이 된다. 앞에서 $b_{click}^{*} = 1 / \lambda^{*}$이 나온 게 단위 관점에서도 자연스럽다.
또 다른 해석은 기회비용이다. 지금 이 임프레션을 사면 나중에 더 좋은 것을 못 산다. $\lambda^{*} c_t$가 그 기회비용의 화폐 환산이고, $r_t - \lambda^{*} c_t > 0$은 기회비용을 제하고도 남는가를 묻는 것이다. 여기서 흥미로운 점은, second price auction은 truthful bidding이 dominant strategy라고 알려져 있는데 예산 제약이 있으면 그렇지 않다는 것이다. $b_t = r_t / \lambda^{*}$는 진짜 가치보다 낮은 값이다. 예산이 남아도는 캠페인이라면 $\lambda^{*} = 0$이 되어 기회비용도 0이 되고, 그때서야 truthful bidding으로 복귀한다.
$\lambda^{*} = 0$인 경우도 complementary slackness가 포괄한다는 점을 짚어두고 싶다. 예산이 남으면 제약이 inactive이므로 $\lambda^{*} = 0$이어야 하고, 이때는 페이싱 자체가 불필요하다. 실무로 번역하면 예산 소진을 못 하는 캠페인에는 pacing이 무의미하다는 뜻이다. controller가 $\lambda$를 0으로 보내고 있다면 그건 오작동이 아니라 이 캠페인은 트래픽이 부족하다는 진단으로 읽어야 할 것 같다.
마지막으로 LP relaxation 관점의 해석도 있다. greedy로 $r_t / c_t$ 내림차순 정렬해서 담을 때 예산이 끊기는 지점의 효율값이 정확히 $\lambda^{*}$이다. $r_t / c_t > \lambda^{*}$이면 사고 아니면 버리는 것이니, 앞의 규칙과 같은 말이다.
Conclusion
primal-dual method 자체는 최적화 수업에서 배운 내용이지만, 광고 도메인 문제에 적용된 형태로 다시 보니 각 조건이 왜 필요한지가 훨씬 선명하게 다가왔다. 특히 complementary slackness가 관측 불가능한 최적성 조건을 예산 소진이라는 관측 가능한 신호로 번역해준다는 점, 그래서 이후의 모든 pacing controller가 그 신호를 추적하는 알고리즘이라는 점이 이번에 정리하면서 가장 크게 얻은 부분이다. 반대로 min max가 어디서 나왔는지, KKT가 왜 성립하는지 같은 부분은 논문이 자세히 설명하지 않고 넘어가서 한참을 헤맸다. 필자와 같이 이 챕터에서 막힌 독자가 있다면 primal을 Lagrangian 형태로 직접 써보는 것을 권하고 싶다. min max와 max min이 대칭이라는 게 보이는 순간 나머지는 따라온다.
first price auction에서는 지불액이 내 입찰가 자신이 되면서 이 유도가 어떻게 달라지는지도 살펴봤는데, 그건 다음 글에서 정리하려고 한다.
댓글