Introduction
In online advertising, platforms must select a subset of available ads to display in multiple slots to maximize user clicks. This scenario is classically modeled as a multiple-play multi-armed bandit problem. However, a major challenge is position bias: an ad placed in the top slot naturally attracts more attention than one at the bottom.
This paper introduces a novel framework called the Position-Based Model under Uncertainty (PBMU). Unlike existing methods that either ignore position bias or assume it is known beforehand, PBMU tackles the realistic scenario where both the quality of the advertisements and the position bias of the slots are unknown. To solve this, the authors develop the Permutation Minimum Empirical Divergence (PMED) algorithm, which achieves theoretically optimal performance by simultaneously learning ad quality and slot bias.
The Challenge: Identifiability and Position Bias
Most existing models rely on the "cascade model," assuming users scan top-to-bottom and stop once they find an interesting ad. However, this assumption is often too restrictive for real-world browsing behavior. The Position-Based Model (PBM) offers a more flexible alternative by assigning a specific discount factor to each slot.
The core difficulty in PBMU is the identifiability problem. If an ad placed in the third slot receives zero clicks, the system cannot immediately determine the cause: is the ad inherently unappealing, or is the third slot rarely viewed? Because the expected reward is the product of ad quality (click-through rate) and slot bias, the system must strategically experiment with different ad-slot combinations to disentangle and learn both parameters simultaneously.
Methodology: The PMED Algorithm
To navigate the PBMU framework, the authors propose the PMED algorithm, which incorporates several advanced optimization techniques:
- Maximum Likelihood Estimation (MLE): PMED continuously updates its estimates of ad quality ($\theta$) and slot bias ($\kappa$). Because these parameters are multiplied together ($\theta \cdot \kappa$), the optimization is "bi-convex"—meaning it is solvable if one parameter is held constant while optimizing the other.
- Minimum Empirical Divergence: The algorithm selects actions that minimize "regret" (lost potential reward) while ensuring enough exploration is conducted to satisfy a theoretical lower bound.
- Bipartite Matching for Allocation: Selecting the best $L$ ads for $L$ slots out of $K$ total ads typically involves an exponential number of combinations. The authors elegantly bypass this by using a bipartite matching algorithm (the Hopcroft–Karp algorithm) to decompose the required exploration into a set of permutations executable in polynomial time.
- Cutting-Plane Method: To handle the non-convex nature of the optimal exploration problem, PMED employs a cutting-plane method that iteratively adds constraints to find the "hardest" parameters to distinguish, ensuring highly efficient exploration.
Key Insights
A critical realization in this work is the inherent redundancy of the model: one could scale the ad quality up and the slot bias down to achieve the identical expected reward. The authors resolve this by normalizing the model, assuming the first slot has a bias of exactly 1.0, which anchors the mathematics.
Furthermore, when both ad quality and position bias are unknown, the optimization becomes a "linear semi-infinite programming" (LSIP) problem. This is significantly harder than standard bandit problems because the constraints are parameterized by an infinite set of possible truths. The paper proves that to be asymptotically optimal, an algorithm must spend a precise amount of time on sub-optimal ad-slot pairs to definitively prove their sub-optimality—a requirement PMED is explicitly designed to meet.
Experimental Results
The paper evaluates PMED against existing algorithms using both synthetic and real-world data.
- Synthetic Data: In a controlled environment with 5 arms and 2 slots, PMED's regret stayed remarkably close to the theoretical minimum (the Regret Lower Bound).
- Real-World Data: Using the Tencent (KDD Cup 2012) dataset—comprising 150 million lines of search engine session logs—the authors extracted realistic CTRs and position biases.
In both scenarios, PMED significantly outperformed baselines like MP-TS (which ignores position bias) and dcmKL-UCB (which assumes a different click model). The baselines often exhibited regret scores orders of magnitude higher, demonstrating that learning position bias dynamically is far more effective than relying on static or incorrect models.
Limitations and Future Work
While theoretically robust, PMED introduces computational overhead. The underlying MLE and cutting-plane optimizations are intensive, prompting the authors to "skip" these optimizations in later rounds to maintain operational speed. Additionally, the optimality proofs are asymptotic ($T \to \infty$); finite-time bounds remain an area for future formalization. Finally, the model assumes stationarity—that ad quality and position bias remain constant over time. Adapting the framework to handle dynamic, real-world shifts (like seasonal ad relevance) represents a promising direction for future research.
Summary updated