\chapter{Online Advertising}

\section{What Makes Ad Recommendation Different?}

Superficially, surfacing advertisements to users seems no different from any other form of personalized recommendation. That is, we can imagine learning user `preferences' and advertisement `properties' from (e.g.)~clicked advertisements in much the same way that any other recommender system is trained.

While ad recommendation does indeed have many similarities to other forms of personalized recommendation, 
%However as we discuss in this chapter, 
there are several properties that demand different solutions compared to what we have seen so far. In particular:
\begin{itemize}
 \item Advertisers have budget constraints. In most recommendation settings we can tolerate considerable imbalance among the items that are recommended (e.g.~a highly popular movie might be recommended to a substantial fraction of all users); this is impossible when recommending ads, given that each advertiser can afford to surface only a limited number of ads (and at the same time, we want to ensure that all advertisers have some ads recommended).
 \item Likewise, each user may only be shown a limited number of ads; while this seems a common enough feature in most recommendation scenarios, it is especially apparent when surfacing ads as users are unlikely to explicitly request additional ads.
 \item Ad recommendations need to be made immediately. Again, this feature is common enough in many recommender systems, but is especially challenging given the considerations above: we cannot find a globally optimal solution that maximizes utility while satisfying advertisers' budget constraints. Instead, we must develop schemes that make local decisions in a way that approximates the globally optimal solution.
 \item Ad recommendation is highly contextual. Whereas most recommender systems rely heavily on user interaction histories, these are presumably less reliable in ad recommendation scenarios (where users' interactions with ads are extremely sparse), if an interaction history is available at all. As such, one has to rely more heavily on user \emph{context} (e.g.~a user's query to a search engine).
 \item Even if a user is responsive to a certain type of ad, there is diminishing value in repeatedly showing similar ads. Instead, we must sometimes recommend ads with low expected utility in the hope of discovering new user interests (this is the basic principle behind an explore/exploit tradeoff).
\end{itemize}

These are the problems we will investigate in order to build systems for online advertising. In Section
%\todo{Finish introduction above}

Note that in this section we will mostly ignore the question of how `compatibility' between a user and an ad is estimated---this could itself be the output of a recommender system, or could simply be a bid that an advertiser places on a user or query.

\section{Matching Problems}

First we will consider the problem of incorporating constraints into (ad) recommendation problems. We want to consider situations where each user can only be shown a fixed number of ads, and each ad can only be shown to a fixed number of users. This is already an oversimplification, as advertisers would usually have a \emph{budget}, and may (for example) bid different amounts per user or query (though we consider these issues in \Cref{sec:?}).

To begin with, we'll consider the case where each ad is shown to exactly one user, and each user is shown exactly one ad. That is, we would like to select a function $\mathit{ad}(u)$ that maps users to ads, such that
\begin{equation}
    \mathit{ad}(u) = \mathit{ad}(v) \rightarrow u = v.
\end{equation}
Alternately, we could write this as an adjacency matrix $A$ such that $A_{u,a} = 1$ if $\mathit{ad}(u) = a$. Then our constraint could be written as
\begin{equation}
    \underbrace{\forall a \sum_u A_{u,a} = 1}_{\text{each advertiser shows one ad}}; \quad \underbrace{\forall u \sum_a A_{u,a} = 1}_{\text{each user sees one ad}}.
\end{equation}
%\todo{realign braces with \clap etc.}
Then, we would like to choose the mapping that maximizes the utility between users and the ads they are shown:
\begin{equation}
    \max_A \sum_{u,a} A_{u,a} f(u,a)
    \label{eq:matchingObj}
\end{equation}
where $f(u,a)$ is a measure of the compatibiliy between a user and an ad.

This type of problem is known as a \emph{matching problem}. Conceptually, it can be viewed as matching two sets of nodes to form a bipartite graph (\Cref{fig:matching}, left), where each possible edge has an associated weight (i.e.,~the compatibility between a user and an ad). Our constraint above now says that every node should be incident on one edge.

\begin{figure}
        \centering
\definecolor{mygrey1}{RGB}{160,160,160}
\definecolor{mygrey2}{RGB}{120,120,120}

\begin{tikzpicture}[thin,
  every node/.style={draw,circle},
  fsnode/.style={fill=mygrey1},
  ssnode/.style={fill=mygrey2},
  ->,shorten >= 3pt,shorten <= 3pt
]

% User vertices
\begin{scope}[start chain=going below,node distance=4mm]
\node[fsnode,on chain] (f1) [label=left: 1, label={[label distance=0.7mm]90:users:}] {};
\foreach \i in {2,3,...,6}
  \node[fsnode,on chain] (f\i) [label=left: \i] {};
\end{scope}

% Ad vertices
\begin{scope}[xshift=2cm,start chain=going below,node distance=4mm]
\node[ssnode,on chain] (s1) [label=right: 1, label={[label distance=2mm]90:ads:}] {};
\foreach \i in {2,3,...,6}
  \node[ssnode,on chain] (s\i) [label=right: \i] {};
\end{scope}
%\todo{Hardcoded vertical spacing of users: label}

\draw (s1) -- (f2);
\draw (s2) -- (f5);
\draw (s3) -- (f1);
\draw (s4) -- (f4);
\draw (s5) -- (f6);
\draw (s6) -- (f3);
% \draw (s9) -- (f5);
% \draw (f5) -- (s6);
\end{tikzpicture}
\hspace{4mm}
\begin{tikzpicture}[thin,
  every node/.style={draw,circle},
  fsnode/.style={fill=mygrey1},
  ssnode/.style={fill=mygrey2},
  ->,shorten >= 3pt,shorten <= 3pt
]

% User vertices
\begin{scope}[start chain=going below,node distance=4mm]
\node[fsnode,on chain] (f1) [label=left: 1, label={[label distance=0.7mm]90:users:}] {};
% \foreach \i in {2,3,...,6}
%   \node[fsnode,on chain] (f\i) [label=left: \i] {};
\node[fsnode,on chain] (f2) [label=left: 2] {};
\node[fsnode,on chain] (f3) [label=left: 3] {};
\node[fsnode,on chain] (f4) [label=left: 4, fill=white] {};
\node[fsnode,on chain] (f5) [label=left: 5, fill=white] {};
\node[fsnode,on chain] (f6) [label=left: 6, fill=white] {};
\end{scope}

% Ad vertices
\begin{scope}[xshift=2cm,start chain=going below,node distance=4mm]
\node[ssnode,on chain] (s1) [label=right: 1, label={[label distance=2mm]90:ads:}] {};
\foreach \i in {2,3,...,6}
  \node[ssnode,on chain] (s\i) [label=right: \i] {};
\end{scope}
%\todo{Hardcoded vertical spacing of users: label}

\draw (s5) -- (f3);
\draw (s1) -- (f2);
\draw (s3) -- (f1);
\end{tikzpicture}
    \caption{Ad recommendation can be viewed as a \emph{bipartite matching problem} (left), where users are shown a fixed number of ads, and each ad is shown to a fixed number of users (in this figure each ad is shown to exactly one user, and vice versa). In an online setting (right), users arrive one at a time; we seek a solution that will be as close as possible to the solution we would have obtained in an offline setting at left.}
    \label{fig:matching}
\end{figure}

Outside of ad recommendation, this type of matching problem appears in many settings, for example it is equivalent to the US's \emph{National Residency Matching Program}, in which medical school students are matched to residency programs: each student can only be matched to a single residency, and each program has a limited number of slots; the matching should be chosen so as to optimize students' preferences for programs (and vice versa). Similar problems appear in various resource allocation settings \cite{gusfield1989stable}; the original paper proposing the solution outlined below considered a setting related to college admissions \cite{gale1962college}.
%\todo{not beautiful writing}

Although \Cref{eq:matchingObj} is a combinatorial optimization problem, it admits efficient approximation (and a polynomial exact solution). The approximation we discuss below is known as \emph{stable marriage}, which draws an analogy between bipartite matching and finding (heterosexual) marriage partners: we seek a solution which, while not necessarily optimal, is `stable,' in the sense that no unmatched pair would have an incentive to `cheat.'

For each man/woman pair $m$ and $w$, we assume a compatibility $f(m,w)$.\footnote{The original solution assumed \emph{different} compatibility functions for men toward women, and women toward men, though we discard this for the application discussed here.} `Stability' then means that there should be no pairs $(m,w)$ and $(m,w')$ such that $m$ and $w'$ are matched but $f(m,w) > f(m,w')$.
%\todo{confusing writing}

and initially assume that there are an equal number of men and women (and that everyone gets married):
%\todo{put this somewhere}

Pseudocode for the stable marriage problem is given below:
\begin{itemize}
    \item All men and all women are initially ‘free’ (i.e.,~not engaged)
    \item while there is a free man $m$, and a woman he has not proposed to
    \begin{itemize}
        \item $w = \max_w f(m,w)$
        \item if ($w$ is free):
        \begin{itemize}
            \item $m$ and $w$ become engaged (and are no longer free)
        \end{itemize}
        \item else ($w$ is engaged to $m'$):
        \begin{itemize}
            \item if $w$ prefers $m$ to $m'$ (i.e.,~$f(m,w) > f(m',w)$):
            \begin{itemize}
                \item $m$ and $w$ become engaged
                \item $m'$ becomes free
            \end{itemize}
        \end{itemize}
    \end{itemize}
\end{itemize}
%\todo{actual pseudocode environment, and above is crappy}
%\todo{algorithm is basically the wikipedia one, but where does it really come from?}

Theorems:
\begin{itemize}
    \item The algorithm eventually terminates; each step includes a new proposal, and there are only $n^2$ possible proposals. Furthermore, each iteration improves the matching score of \Cref{eq:matchingObj} (or does nothing).
    \item The solution is stable. The proof is relatively straihtforward: one assumes an unstable solution in which 
    %$m$ is married to $w'$ but would prefer to be married to $w$; 
    $m$ and $w$ would prefer to be married to each other rather than their current spouses $m'$ and $w'$;
    in this case $m$ must have proposed to $w$ first (since he always proposes to his most compatible match first); so either $w$ was already engaged to somebody preferable, or $w$ accepted and later broke off the engagement; neither of these two scenarios could have ocurred if $m'$ is less compatible.
    \item Note that a consequence of the above is the possibly surprising conclusion that every matching problem as a stable solution.
    \item The solution requires $O(n^2)$ steps, since each step includes a proposal, and there are at most $n^2$ possible proposals. In practice the running time is often substantially faster.
    %\todo{What about sorting the ranked lists for each man?}
    %\todo{Cite for O(nlogn) running time?}
    \item The solution is not guanarteed to be optimal, and the optimal solution is not guaranteed to be stable. Examples of both are given in \Cref{fig:matchingOpt}.
\end{itemize}


\begin{figure}
        \centering
\definecolor{mygrey1}{RGB}{160,160,160}
\definecolor{mygrey2}{RGB}{120,120,120}

\begin{tikzpicture}[thin,
%  every node/.style={draw,circle},
  fsnode/.style={fill=mygrey1},
  ssnode/.style={fill=mygrey2},
  ->,shorten >= 3pt,shorten <= 3pt
]

% User vertices
\begin{scope}[start chain=going below,node distance=8mm]
%\node[fsnode,on chain,draw,circle] (f1) [label=left: 1, label={[label distance=0.7mm]90:women:}] {};
\node[fsnode,on chain,draw,circle] (f1) [label=left: 1] {};
\node[fsnode,on chain,draw,circle] (f2) [label=left: 2] {};
\end{scope}

% Ad vertices
\begin{scope}[xshift=2cm,start chain=going below,node distance=8mm]
%\node[ssnode,on chain,draw,circle] (s1) [label=right: 1, label={[label distance=2mm]90:men:}] {};
\node[ssnode,on chain,draw,circle] (s1) [label=right: 1] {};
\node[ssnode,on chain,draw,circle] (s2) [label=right: 2] {};
\end{scope}
%\todo{Hardcoded vertical spacing of men/women NOT CORRECT: label}

\node[above=of f1] (w1) {women};
\node[above=of s1] (m1) {men};

\draw[dotted,thick] (s1) edge[-] (f1);
% \node [pos=0.66,above=s1] {Transpose};
\draw[thick] (s1) edge[-] (f2);
\draw[thick] (s2) edge[-] (f1);
\draw[dotted,thick] (s2) edge[-] (f2);




% \draw (s9) -- (f5);
% \draw (f5) -- (s6);
\end{tikzpicture}

    \caption{Examples of matching solutions that are stable but not optimal (left), and optimal but not stable (right).
    %\todo{figure}
    \label{fig:matchingOpt}
    }

\end{figure}



%tikz:
%https://tex.stackexchange.com/questions/15088/bipartite-graphs

\section{AdWords}

So far, we have discussed the issue of developing recommendation approaches that consider some notion constraints or `budgets' for the perspective of users and advertisers. While incorporating constraints is potentially useful in a variety of recommendation scenarios, our solution still doesn't fully address the setting of \emph{ad} recommendation; in particular, when recommending ads, we are unlikely to see the entire set of users (or queries) in advance, before having to select advertisements.

As such, we desire an algorithm that makes decisions (i.e.,~assigns ads to users) one at a time, while still conforming to matching (or budget) constraints, as in \Cref{fig:advertising} (right).

Formally, the above describes the distinction between an \emph{offline} and an \emph{online} algorithm, i.e.,~one which sees the entire problem in advance, versus one 

\emph{AdWords} \cite{mehta2007adwords} is a specific instance of this type of recommendation problem developed for \emph{Google's} online advertising platform.

Mostly, the setting follows the one we described above, though includes a few additional components. Specifically,
\begin{itemize}
    \item Each advertiser $a$ has a \emph{bid} $f(q,a)$ that they are willing to make for each query $q$.
    \item The bid generally refers to how much the advertiser will pay \emph{if} the ad is clicked on; this is determined by an estimated \emph{click-through-rate}, $\mathit{ctr}(q,a)$. As such the expected profit would be $f(q,a) \times \mathit{ctr}(q,a)$, which one can think of as being analogous to the compatibility from \Cref{sec:sectionAbove}.
    \item Each advertiser has a \emph{budget} $b(a)$ (e.g.~for a one-week period).
    \item As in \Cref{sec:sectionAbove}, there is a limit on the number of ads that can be returned for each query.
\end{itemize}


Of course the actual implementation of AdWords contains many features not described here, for instance Adwords
%\todo{italics}
uses a second-price auction (the winning advertiser pays the amount that the \emph{second} highest bidder bid), and advertisers don't bid on exact queries, but rather are matched using a `broad matching' criteria that can include subsets, supersets, or synonyms of keywords being bid on. We refer to \cite{rajaraman2011mining} for further description of these details, and \cite{mehta2007adwords} for a more detailed technical description.

\section{Bandit Algorithms}

So far, when developing matching algorithms in \Cref{sec:matching?} and AdWords in \Cref{sec:adwords},
%\todo{anything else?}
we've assumed that a compatibility function between between users and ads was available in advance, and merely considered the question of how ads should be \emph{allocated} to users based on budgets and the given compatibility.

However, ad recommendation (among other settings) could present unique challenges in terms of how we estimate compatibility in the first place.

Compared to other recommendation settings, it is unlikely that we could learn user-to-ad compatibility by collecting historical data of ads users have previously interacted with. Some potential issues include:
\begin{itemize}
    \item Interaction data is extremely sparse; users likely interact with only a tiny fraction of the advertisements that are surfaced to them, making positive feedback extremely rare.
    \item Even if a user is interested in a particular topic, there are diminishing returns in repeatedly surfacing similar ads (e.g.~a user searching for rental tuxedos likely remains interested in the topic for a short time).
    \item Users do not `seek out' ads from which we might learn their interests. Thus we must sometimes surface ads before we have collected evidence that a user is interested in them. 
    \item Recommendation is highly contextual. E.g.~an ad for rental tuxedos is only worth surfacing if a user is currently searching for a closely related topic.
\end{itemize}

%\section{Case Study?}

\subsection{Bandit Algorithms for Recommendation}

A Contextual-Bandit Approach to Personalized News Article Recommendation \cite{li2010contextual}


The basic setup of a \emph{contextual bandit} (following e.g.~\cite{li2010contextual}) is as follows.
%\begin{itemize}
%\item 
During each step $t$, we observe a user $u_t$ and a set of actions (or `arms') $\mathcal A_t$. The actions $a \in \mathcal A_t$ reflect, for example, the space of possible advertisements that could be surfaced to a user during a particular timestep.

%\item 
In the setting of a contextual bandit, each timestep $t$ and action $a$ is associated with a feature vector $x_{a,t}$ representing the current \emph{context}; $x_{a,t}$ is intended to capture any features associated with the user and the action at a particular point in time (which could include information about their search query, etc.).

%\item
During every timestep, an action is selected, following which a reward $r_{a,t}$ is received. This reward might measure (e.g.)~whether the user clicked on the surfaced advertisement, or the payout received from doing so. Critically, the reward is only observed \emph{for the action $a$ that was selected}, that is, we cannot observe whether the user would have clicked on an ad that \emph{wasn't} shown.

%\item
Over time, the goal is to devise a strategy for selecting actions in such a way that the total reward is maximized. 


%\end{itemize}
%\todo{itemize or not?}


\begin{equation}
    E(r_{a,t}|x_{a,t}) = x_{a,t} \cdot \theta_u
\end{equation}

\section{News Recommendation}

Doesn't exactly go here but might go somewhere?

Turning down the noise

News search engines and the challenge to traditional journalistic
roles