Browser Bandit to Curb Computation

[appascoe]

I'm documenting an idea from a discussion a few months ago: the use of a bandit algorithm to reduce the amount of computation for auctions within FLEDGE. This is motivated by some of the internal research we've been doing against
the FLEDGE API currently available in Chromium. I have a colleague who will file a forthcoming issue with our findings and will link to it in this issue when it's published.

One previously documented proposal in (#79) suggests that ad-tech vendors could provide a priority score for a given interest group. Within a set of interest groups provided by the same
ad-tech vendor, the priority score would indicate which ads should have their generateBid() function evaluated with priority. Ads with a lower priority are more likely to not be able to place a bid due to any timeouts within the
browser, or on the publisher page. I see a couple issues with this proposal:

• While the proposal has some ability to update the priority score, say through a trusted server response, the issue is that priority scores are usually highly dependent on the context in which an ad will be shown (e.g. car ads on
  publisher pages about cars). A flat priority score doesn't suffice.
• Priority scores can only be updated if the generateBid() function is being called, resulting in some ads potentially having very stale scores. (Note: This could be resolved through some background process that allows for these
  updates to happen.)
• The priority score only works within a set of IGs for a specific ad-tech vendor. To maintain a fair market, this would essentially force the browser to evaluate at least one ad for every ad-tech vendor that has an IG in the
  browser. a) This kicks the scalability concern down the road, and b) potentially this creates an incentive for an ad-tech vendor to use multiple "owners" just to increase voice in auctions.

Instead, I propose implementing a simple bandit algorithm within the browser to prioritize which ads have their generateBid() function evaluated for participation in the auction. The basic mechanics for this is taken whole-hog
from an old Google paper (http://www.economics.uci.edu/~ivan/asmb.874.pdf), "A modern Bayesian look at the multi-armed bandit," by Steven L. Scott.

As a first, naive approach, the browser just keeps track of the wins and losses for each ad unit within the browser. These then become parameters into the beta distribution: beta(wins+1, losses+1). This is effectively the
posterior of the probability that a given ad will win an auction (in general). Each ad has its own distribution. At, or potentially before, bid time, the browser can draw a single variate from the distribution for each ad, and this
effectively becomes the priority score. (For the reader who wishes to read more, this is a quick approximation to Thompson sampling, which naturally balances exploration and exploitation.) It is possible to draw more than one
variate to get a better sense of which ads are most likely to win, but across many ad units shown to an individual browser, and across many browsers, even a single variate should average out nicely in the long run.

There is one issue here in that the count of wins and losses will only increment for ads that have been selected by the bandit for participation in the auction. As a next level of complication to fix this, there's a difference
between showing an ad quickly to the user, and thus subject to a timeout constraint, and what "would have really happened." The browser itself collects everything it needs (contextual data, bidding functions, scoring functions,
etc.) to effectively run a background ghost auction post-hoc: simply run the auction with all ad units having their generateBid() functions evaluated in the background. Thus, for each ad unit, we would have beta(ghost wins + 1, ghost losses + 1).

Note that this bandit still doesn't take into account the context of the publisher page or any other interaction terms with the ad units themselves. A further level of complication would be to create a contextual bandit. There are
a few ways of doing this. A simple one might be to keep track of ghost wins and ghost losses by page category for each ad unit. This would be a very modest increase on storage requirements, but is computationally the same. Another
would be to train a model (probably some type of GLM for quick training and inference; and it probably wouldn't require too many parameters). One benefit of doing some sort of modeling would be that we could incorporate other major
features of ad units (such as how often the user has already seen a given ad) to determine its likelihood of winning the auction.

Anyway, as stated above, I wanted to make sure this idea gets documented. We didn't have much time to discuss it in the last FLEDGE meeting where it was raised, and perhaps it sounded overly complicated in the moment, but I really
don't think it is, or, at least, we don't need to start with anything majorly complicated. I think even the most basic solution is a vast improvement over priority scores. Definitely curious to hear feedback.