On the Robustness of Epoch-Greedy in Multi-Agent Contextual Bandit Mechanisms

Auctions for allocating online advertisements are run many billions of times per day and constitute the main business models for many digital platforms. How these auctions are designed and managed can therefore have major implications for both the auctioneers as well as the many many participants competing for ad space. Under a simple model of bidding behavior, and with good information about the quality of submitted ads, classical theory in mechanism design provides the auctioneer with what is essentially the uniquely optimal allocation and payment scheme. The VCG mechanism vickrey1961counterspeculation allocates each advertisement slot to the highest bidder, weighted by the “click-through-rate” (CTR), and charges an amount equal to the second highest bid . This scheme to select and charge bidders is welfare-maximizing and truthful, i.e. such that the bidders do not have any incentive to misreport their true value for clicks.

The simple VCG strategy, while nice in theory, is unfortunately lacking in one critical way: it requires that the auctioneer possess knowledge of the click-through-rates of the various ads submitted by bidders. From this perspective, selecting an ad to display to the user is akin to pulling an arm in a bandit problem, where the welfare associated to a pull is value the bidder receives in the event of a click. Indeed, this $K$-armed bandit perspective on repeated ad auctions has been quite thoroughly studied; in particular, DBLP:journals/siamcomp/BabaioffSS14; devanur2009price model each arm as an advertiser with an associated fixed click-through-rate. The key hurdle for applying bandit methods to repeated auctions is the conflict between minimizing regret and maintaining reasonable long-term incentives for the bidders, since the auctioneer’s learning strategy may lead to unpredictable bid behavior. DBLP:journals/siamcomp/BabaioffSS14; devanur2009price design a VCG style mechanism using an explore-then-commit bandit strategy. The resulting mechanism is truthful and obtains the $O(T^{2/3})$ lower bound on the welfare regret which is measured with respect to the fixed arm with the highest expected welfare.

In this paper, we turn our attention to the contextual version of the same bandit mechanism design problem. In the above setting, while the auctioneer’s estimates of the CTRs may change, the underlying CTRs for all the arms are fixed. But indeed these CTRs may not only be unknown but also fluctuate according to some context that arrives before each auction and provides details about ad desireability (e.g. profile of the user, time of day, etc.). When the mechanism is given access to this context, as well as a family of experts (i.e. hypotheses, policies, etc.), it will want to minimize regret not with respect to simply the best arm (ad) but the optimal expert for selecting an arm according to any given context. This more general setting provides additional power to the mechanism designer, who can now consider much more complex policies for allocation that achieve higher welfare.

Although contexts have been extensively studied in the multi arm bandits literature lu2010contextual; chu2011contextual; LangfordZhang07; AuerCeFrSc2003 , there has been little focus on the interplay between contexts and strategic arms who care about their own long term utility. Giving more flexibility to the mechanism to select ads, in the form of contexts and policies, presents new challenges to the mechanism design problem as it can affect bidder incentives in ways that have not been previously addressed. Consider just this one example: a participant can bid higher for a particular ad slot, but this action can (all else equal) decrease their likelihood of winning the slot, as the change can lead to the learning algorithm to move to a different policy. In order to manage this awkward incentive issue we slightly weaken our notion of truthfulness by considering a property we call $\alpha$-rationality, where agents can only violate truthful bidding if it improves their utility by at least $\alpha$. Ultimately, we are able to show that the mechanism can guarantee regret on the order of $\tilde{O}\left(T^{2/3}K^{4/3}+T^{1/3}K^{2/3}/\alpha^{2}\right)$, with respect to the optimal arm selection policy, by using a relatively standard $\epsilon$-Greedy style algorithm. Pay per click auctions in the contextual multi-slot setting has also been studied before by gatti2012truthful where the principal directly tries to learn the click through rate as a function of the contexts for each arm under strong assumptions about the class of functions it is learning over. Their results do not apply to our setting as we don’t directly aim to learn the click through-rate for each context and arm but utilise the information given by the contexts through a class of experts.

Apart from the challenges induced by contexts and strategic agents, online ad auctions are also vulnerable to data corruption attacks such as click fraud wilbur2009click . For example, an agent may create a bot that either clicks her own ads or does not click competing ads to adversarially bias the click-through-rate estimates and make the ad seem less desirable to the principal. Corruption robustness in multi arm bandits has been studied at great length in recent years lykouris2018stochastic; gupta2019better , but never in multi arm bandit mechanisms. Although these algorithms have great performance in the stochastic bandit setting, they lack a key property called exploration separation DBLP:journals/siamcomp/BabaioffSS14 which has been shown to be fundamental for ensuring truthfulness in bandit mechanisms.

Finally, we show that the contextual $\epsilon$-greedy mechanism (Algorithm LABEL:alg:contextmab) has a surprisingly nice additional property: it is tolerant to a certain amount of adversarial click corruptions. In the easier case of stochastic multi arm bandit mechanism, we show that the contextual $\epsilon$-greedy mechanism is truthful without any relaxation on the rationality of the agent and is inherently robust to adversarial click corruptions without any changes to the mechanism. If the number of rounds corrupted by the adversary is $C$, which is unknown to the auctioneer, the welfare regret of the mechanism in this setting is $\tilde{O}(K^{1/3}T^{2/3}+C)$, which recovers the lower bound up to poly log terms. In the presence of contexts and $\alpha$-rational agents, the welfare regret of the contextual $\epsilon$-greedy mechanism is $\tilde{O}\left(T^{2/3}K^{4/3}+T^{1/3}K^{2/3}/\alpha^{2}+C/\alpha+KC\right)$.

We study the problem of pay-per-click (or PPC) ad auctions in a multi-armed contextual bandit setting. There is a set of advertisers (also referred to as agents or arms) which we denote as $\mathcal{A}$ and has cardinality $K$; agents repeatedly compete for a single slot over $T$ time steps (that correspond to users). If an advertiser $a\in\mathcal{A}$ is selected, then a click occurs with probability equal to the click-through-rate. Upon a click, the agent earns value equal to $\mu(a)\in[0,1]$ (advertisers earn a fixed reward whenever a click happens, but different users may have different probability of clicking their ad which depends on the context of the user). Contexts come from a context space $\mathcal{X}$ and are identically and independently distributed (i.i.d.) across rounds. The click-through-rate function $\rho:\mathcal{A}\times\mathcal{X}\rightarrow[0,1]$ maps agents and contexts to the probability of being clicked upon display.

In each round $t=1,\cdots,T$, a context $x^{t}\in\mathcal{X}$ is drawn i.i.d. from a fixed distribution. Each agent $a\in\mathcal{A}$ submits a bid $b^{t}(a)$ and, in response the platform selects an agent $a^{t}$ and displays her ad. The selected ad is clicked with probability $\rho(a^{t},x^{t})$ and the corresponding clicked result $c^{t}$ is $1$ if the ad is clicked and $0$ otherwise. The platform receives the click result $c^{t}$ and if the ad gets clicked, i.e. $c^{t}=1$, then it charges the agent $a^{t}$ a payment $p^{t}$ and the agent $a^{t}$ gains utility $u^{t}(a^{t})=\mu(a^{t})-p^{t}$. If the ad is not clicked, $c^{t}=0$, then the payment and the utility of the agent is $0$.

Following classical works on contextual bandits, we also assume a class of hypotheses (also referred to as experts) which we denote as $\mathcal{H}$ with $|\mathcal{H}|=m$. Each expert $h:\mathcal{X}\rightarrow\mathcal{A}$ is a mapping from the context space to agents where $h(x)$ is the agent recommended by the expert $h$ given context $x$. The auctioneer can use the experts’ recommendations to make decisions.

Let $h^{\star}=\operatorname*{argmax}_{h\in\mathcal{H}}\{R(h,\vec{\mu})\}$ be the expert with the highest expected welfare. The performance of our algorithm against $h^{\star}$ is measured by the notion of regret:

If we assume that agents report their value truthfully (defined below) then this reduces to the contextual bandit setting AuerCeFrSc2003; LangfordZhang07.

A special case of this setting is the multi-armed bandit setting where the hypothesis class is the same as the agent space $\mathcal{H}=\mathcal{A}$ and each hypothesis always suggests the same agent. In this special case the expected welfare of hypothesis $h=a$ is $R(h,\vec{\mu})=\mu(a)\cdot\mathbbm{E}_{x}[\rho(a,x)]$.

In this work, we introduce the study of truthful mechanism design in contextual bandit mechanisms. Our definition of truthfulness generalizes the one in multi-armed bandits:

We now introduce some definitions needed to characterize the setting. Suppose the expert that the mechanism follows is $h$, and the context is $x$, then the probability that agent $a$ gets a click is its click probability under context $x$ times the indicator of whether $h$ suggests agent $a$, i.e., $\rho(a,x)\mathbbm{1}\{h(x)=a\}$. Since the context in each round is identically and independently distributed, the probability that the agent will receive a click is this value in expectation over all contexts, which gives the following definition.

For the rest of the paper, we assume that the agents cannot observe the context. This is necessary as we show in the appendix LABEL:sec:observe that if agents are allowed to observe the context, then it is hard to design truthful and low-regret mechanism without any assumptions on the expert class. This is a justifiable assumption as the context may contain sensitive information about the users which should not be shared with the advertiser.

Note that based on the definition of $\Pi(a,h)$, the expected welfare of the mechanism following an expert $h$ can be written as $R(h,\bm{\mu})=\sum_{a\in\mathcal{A}}\mu(a)\cdot\Pi(a,h)$. Next we introduce the definition of reported welfare which is a proxy for expected welfare.

Note that when the mechanism is truthful, agents will bid their true values, i.e. $\bm{b}=\bm{\mu}$, then the reported welfare of an expert will be identical to its expected welfare. In this case, the expert with the highest reported welfare is exactly the best expert, that is, $\operatorname*{argmax}_{h\in\mathcal{H}}R(h,\bm{b})=h^{*}$.

Next we want to characterize the incentives of agents. One important quantity the incentives are based on is the relation between how much they bid and how likely they will get a click. Recall that the mechanism allocates slots to agents based on experts class $\mathcal{H}$, data in the history $H^{t}$ which includes all the information available to the principal up to round $t$, agents’ bids $\bm{b}$, and the context $x$. So for an agent $a$, the probability that it could win the slot if bidding $b(a)=b$ is $\Pr\{A^{t}(\mathcal{H},H^{t},x,b,\bm{b}^{t}_{-a})=a\}$, where $A^{t}$ is the allocation rule of the mechanism at round $t$ and $\bm{b}^{t}_{-a}$ is the bids of the other agents, which multiplied by the click through rate $\rho(a,x)$ would be the probability that it could receive a click. Since the agent cannot observe the context, the general probability to receive a click should be that value in expectation over all context, which gives the following definition.

Based on the definition of $g^{t}(a,b)$, we are able to formally write the expected utility function of an agent $a$ when her bid is $b$ as:

where $p^{t}(a,b)$ is the payment at round $t$ if agent $a$ is selected and clicked and her bid is $b$. Note that the function $p^{t}(\cdot,\cdot)$ can depend on the allocation rule, bids from other arms, data of history, and experts class.

Finally, we introduce the definition of exploration separated allocation rule which has been shown to be fundamental for truthful bandit mechanisms DBLP:journals/siamcomp/BabaioffSS14.

In the stochastic setting without contexts, since each expert is an arm and we are competing with the best arm in expectation, as shown in DBLP:journals/siamcomp/BabaioffSS14; kakade2013optimal, a simple VCG style mechanism recovers the lower bounds for the regret. In the presence of a more complex class of experts which can utilize the context to make better decisions, the benchmark becomes harder as we are now competing with the best expert in expectation. To compete with the best expert, the platform has to consider expert predictions while making decisions and the interaction between the agents and the experts makes truthfulness harder.

We focus our attention on designing mechanisms using exploration separated allocation rules. For such allocation rules, in any non-influential round, i.e. the round whose click results and bids don’t influence the future decisions of the principal, the bid reported by an agent can only influence the utility obtain in the current round. Hence the agents optimize their bid only to maximise the utility from the current non-influential round. In other words, for each $a$ and $t$ that is non-influential, if $u^{t}(a,b)$ is maximized at $b=\mu(a)$, then all agent will always bid truthfully in every non-influential round. This fact gives a necessary condition for a mechanism which uses an exploration separated allocation rule to be truthful.

In fact, this payment rule can be viewed as the Pay-Per-Click auction version of the Myerson payment identity (myerson1981optimal). This theorem shows that for any mechanism using an exploration separated allocation rule, it can only be truthful for some payment rule only if $g^{t}(a,b)$ is always monotonically increasing in $b$ in any non-influential round $t$.

Note that to have monotone $g^{t}(a,b)$, one simple allocation rule could be randomly picking an arm at each round, but clearly such allocation rule is far worse then the benchmark we want to achieve. We need a more complicated allocation rule which can guarantee monotonicity of $g^{t}(a,b)$ while recovering the benchmark.