Selecting multiple web adverts: A contextual multi-armed bandit with state uncertainty

Abstract

We present a method to solve the problem of choosing a set of adverts to display to each of a sequence of web users. The objective is to maximise user clicks over time and to do so we must learn about the quality of each advert in an online manner by observing user clicks. We formulate the problem as a novel variant of a contextual combinatorial multi-armed bandit problem. The context takes the form of a probability distribution over the user's latent topic preference, and rewards are a particular nonlinear function of the selected set and the context. These features ensure that optimal sets of adverts are appropriately diverse. We give a flexible solution method which combines submodular optimisation with existing bandit index policies. User state uncertainty creates ambiguity in interpreting user feedback which prohibits exact Bayesian updating, but we give an approximate method that is shown to work well.

Keywords:

• Multi-armed bandits
• contextual bandits
• statistical learning
• diverse recommendation

Acknowledgements

This work was funded by a Google Faculty Research Award. James Edwards was supported by the EPSRC funded EP/H023151/1 STOR-i CDT.

Disclosure statement

No potential conflict of interest was reported by the authors.

Appendix A: Derivations for Section 4

A1. Updating equations for arm weights

PCM. The joint distribution for all weights given a feedback step is updated as given below. In the following note that $p(·|\mathbf{q},x)$ simplifies to $p(·|x)$ and that $p({\mathbf{w}}_{\mathcal{A}},x|\mathbf{q},A)=p({\mathbf{w}}_{\mathcal{A}})q_x$ since x is independent of ${\mathbf{w}}_{\mathcal{A}}$. The posterior belief for the weights after a user action is, $$\begin{array}{l}p\left({\mathbf{w}}_{\mathcal{A}}\right|y,m^{*},\mathbf{q},A)=\sum _{x=1}^{n}p({\mathbf{w}}_{\mathcal{A}},x|y,m^{*},\mathbf{q},A)\\ =\sum _{x=1}^n\frac{p(y,m^{*}|{\mathbf{w}}_{\mathcal{A}},x,\mathbf{q},A\left)p\right({\mathbf{w}}_{\mathcal{A}},x|\mathbf{q},A)}{p(y,m^{*}|\mathbf{q},A)}\\ =\frac{1}{p(y,m^{*}|\mathbf{q},A)}\sum _{x=1}^n\left\{\left[{\left(w_{a_{m^{*}},x}\right)}^y\prod _{a\in A\prime }(1-w_{a,x})\right]p\left({\mathbf{w}}_{\mathcal{A}}\right)q_x\right\}\\ =\frac{p\left({\mathbf{w}}_{\mathcal{A}}\right)}{p(y,m^{*}|\mathbf{q},A)}\sum _{x=1}^n\left[q_x{\left(w_{a_{m^{*}},x}\right)}^y\prod _{a\in A\prime }(1-w_{a,x})\right].\end{array}$$

TCM. The updating equation for ${\mathbf{w}}_{\mathcal{A}}$ for TCM is similar to that for PCM except that $p(y,m^{*}|{\mathbf{w}}_{\mathcal{A}},x,\mathbf{q})$ changes due to the user threshold u: (A1) $$\begin{array}{l}p\left({\mathbf{w}}_{\mathcal{A}}\right|y,m^{*},\mathbf{q},A)=\sum _{x=1}^{n}p({\mathbf{w}}_{\mathcal{A}},x|y,m^{*},\mathbf{q},A)\\ =\sum _{x=1}^n\frac{p(y,m^{*}|{\mathbf{w}}_{\mathcal{A}},x,\mathbf{q},A\left)p\right({\mathbf{w}}_{\mathcal{A}},x|\mathbf{q},A)}{p(y,m^{*}|\mathbf{q},A)}\\ =\frac{p\left({\mathbf{w}}_{\mathcal{A}}\right)}{p(y,m^{*}|\mathbf{q},A)}{\int }_{u=0}^1\sum _{x=1}^n\left[q_x{\left(1_{\{w_{a_{m^{*}},x}>u\}}\right)}^y\prod _{a\in A\prime }{1}_{\{w_{a,x}\le u\}}\right]du.\end{array}$$(A1)

A2. Derivation of $\tilde{\mathbf{q}}$

The posterior $\tilde{\mathbf{q}}=({\tilde{q}}_1,\dots ,{\tilde{q}}_n)$ depends on ${\mathbf{W}}_{\mathcal{A}}$, y, $m^{*}$, q and A. For ease of reading the rest of this section will use w and W to respectively stand for ${\mathbf{w}}_{\mathcal{A}}$ and ${\mathbf{W}}_{\mathcal{A}}$. Bayes Theorem will be used to condition the outcome on x which allows the use of the conditional independence of arms under PCM to factorise to a simple formula. $$\begin{array}{l}{\tilde{q}}_x=p\left(x\right|\mathbf{W},y,m^{*},\mathbf{q},A)\\ =\int p(x,\mathbf{w}|\mathbf{W},y,m^{*},a,A)\mathrm{d}\mathbf{w}\\ =\int p\left(x\right|\mathbf{w},y,m^{*},\mathbf{q},A\left)p\right(\mathbf{w}|\mathbf{W},y,m^{*},\mathbf{q},A)\mathrm{d}\mathbf{w}\\ =\int \frac{p(y,m^{*}|x,\mathbf{w},\mathbf{q},A\left)p\right(x|\mathbf{w},\mathbf{q},A)}{p(y,m^{*}|\mathbf{w},\mathbf{W},\mathbf{q},A)}p\left(\mathbf{w}\right|\mathbf{W},y,m^{*},\mathbf{q},A)\mathrm{d}\mathbf{w},\end{array}$$

Then, substituting in $$\begin{array}{l}p\left(\mathbf{w}\right|\mathbf{W},y,m^{*},\mathbf{q},A)=\frac{p(\mathbf{w},y,m^{*}|\mathbf{W},\mathbf{q},A)}{p(y,m^{*}|\mathbf{W},\mathbf{q},A)}\\ =\frac{p(y,m^{*}|\mathbf{w},\mathbf{W},\mathbf{q},A\left)p\right(\mathbf{w}\left|\mathbf{W}\right)}{p(y,m^{*}|\mathbf{W},\mathbf{q},A)},\end{array}$$ and cancelling gives (A2) $$\begin{array}{l}{\tilde{q}}_x=\int \frac{p(y,m^{*}|x,\mathbf{w},\mathbf{q},A)p(x|\mathbf{w},\mathbf{q},A)p(\mathbf{w}|\mathbf{W})}{p(y,m^{*}|\mathbf{W},\mathbf{q},A)}\mathrm{d}\mathbf{w}\\ =q_x\int \frac{p(y,m^{*}|x,\mathbf{w},\mathbf{q},A)p(\mathbf{w}|\mathbf{W})}{\sum _{\tilde{x}}{q}_{\tilde{x}}\int p(y,m^{*}|\tilde{x},\tilde{\mathbf{w}},\mathbf{q},A)p(\tilde{\mathbf{w}}|\mathbf{W})\mathrm{d}\tilde{\mathbf{w}}}\mathrm{d}\mathbf{w},\end{array}$$(A2)

where the last step uses $p(x|\mathbf{w},\mathbf{q},A)=p(x|\mathbf{q})=q_x$.

It remains to find $\int p(y,m^{*}|x,\mathbf{w},\mathbf{q},A)p(\mathbf{w}|\mathbf{W})\mathrm{d}\mathbf{w}$. Under PCM this is easily found since, given x, the probability of clicking any arm a considered by the user is the same as its independent click probability (as though it were the only arm in the set) and is independent from all weights except $w_{a,x}$. That is, for a single arm a, (A3) $$\begin{array}{l}\int p(y,m^{*}|x,\mathbf{w},\mathbf{q},A\left)p\right(\mathbf{w}\left|\mathbf{W}\right)\mathrm{d}\mathbf{w}=\int p(y,m^{*}|x,w_{a,x},\mathbf{q},A\left)p\right(w_{a,x}\left|W_{a,x}\right)\mathrm{d}{w}_{a,x}\\ ={\left({\mu }_{a,x}\right)}^y{(1-{\mu }_{a,x})}^{(1-y)},\end{array}$$(A3) where ${\mu }_{a,x}=\frac{{\alpha }_{a,x}}{{\alpha }_{a,x}+{\beta }_{a,x}}$ is the expectation of $W_{a,x}$. Under PCM, the outcome of any arm, given it is considered by the user, is independent of the other arms so (A2) and (A3) can be combined to give $${\tilde{q}}_x=q_x\frac{{\left({\mu }_{a_{m^{*}},x}\right)}^y\prod _{a\in A^{\prime }}(1-{\mu }_{a,x})}{\sum _{j=1}^n\left[q_j{\left({\mu }_{a_{m^{*}},x}\right)}^y\prod _{a\in A^{\prime }}(1-{\mu }_{a,x})\right]}.$$

A3. Updating for TCM with known x

Adapting (A1) in Section A1, the updating for known x under TCM is $$\begin{array}{l}p\left({\mathbf{w}}_{\mathcal{A}}\right|y,m^{*},x)=\frac{p\left({\mathbf{w}}_{\mathcal{A}}\right)}{p(y,m^{*}|\mathbf{q})}{\int }_{u=0}^1{q}_x{\left(1_{\{w_{a_{m^{*}},x}>u\}}\right)}^y\prod _{a\in A\prime }{1}_{\{w_{a,x}\le u\}}du\\ =\frac{q_{x}p\left({\mathbf{w}}_{\mathcal{A}}\right)}{p(y,m^{*}|\mathbf{q})}{\int }_{u=0}^1{\left(1_{\{w_{a_{m^{*}},x}>u\}}\right)}^y{1}_{\{u>{\max }_{a\in A\prime }(w_{a,x}\left)\right\}}du\\ =\frac{q_{x}p\left({\mathbf{w}}_{\mathcal{A}}\right)}{p(y,m^{*}|\mathbf{q})}\left[{\left(w_{a_{m^{*}},x}\right)}^y-\underset{a\in A\prime }{\max }\left(w_{a,x}\right)\right].\end{array}$$

Appendix B: Lemma B.1

The following lemma is used in the proof of Theorem 5.1 which is given in Appendix C. Both this lemma and the proof of Theorem 5.1 use the following notation.

Let $R^{TS}(a,{\mathbf{W}}_{a,t},{\mathbf{q}}_t|I_t)={\mathbf{q}}_t·{\tilde{\mathbf{w}}}_{a,t}$ denote the stochastic index for the multiple action Thompson sampling policy for a single arm a where each ${\tilde{w}}_{a,t,x}\sim W_{a,t,x}$. Then under SEQ the arm chosen in slot one is the one with the highest index: $a_{t,1}={\text{argmax}}_{a\in \mathcal{A}}{R}^{TS}(a,{\mathbf{W}}_{a,t},{\mathbf{q}}_t|I_t)$.

Lemma B.1.

Let ${\tau }_{a,T}$ be the set of times $t=1,\dots ,T$ at which $a\in A_t$. Let $q^{*}=\underset{t,x}{\inf }\mathrm{Pr}(q_{t,x}=1)$ and $w^{*}={\max }_{a\in \mathcal{A},x}{w}_{a,x}$ and, from these, set $\eta =q^{*}{(1-w^{*})}^m$. If $q^{*}>0$ then under the deterministic updating scheme given in Section 4.2 using any click model from Section 3.2, $$\mathrm{Pr}\left(R^{TS}(a,{\mathbf{W}}_{a,T},{\mathbf{q}}_T|I_t)\le \frac{1}{1+\eta -{\delta }_1}+{\delta }_2\right)\to 1\hspace{1em} \text{as} \left|{\tau }_{a,T}\right|\to \infty$$ for any $a\in \mathcal{A}$ and any δ₁, δ₂ such that $\eta >{\delta }_1>0$ and ${\delta }_2>0$.

Proof.

For any $a\in \mathcal{A},x=1,\dots ,n$ we will give bounds for expected rate at which ${\alpha }_{a,t,x}$ and ${\beta }_{a,t,x}$ increase as the arm a is selected over time (an upper bound for ${\alpha }_{a,t,x}$ and a lower bound for ${\beta }_{a,t,x}$). This will give an asymptotic upper bound less than 1 on each posterior mean ${\mu }_{a,t,x}=\mathbb{E}\left[W_{a,t,x}\right]$ as $\left|{\tau }_{a,t}\right|\to \infty$. Showing that $Var(W_{a,t,x})\to 0$ as $\left|{\tau }_{a,t}\right|\to \infty$ then gives the required result. Throughout, a is an arbitrary arm in $\mathcal{A}$ and x an arbitrary state in $\{1,\dots ,n\}$.

Let ${\alpha }_{a,0,x}$ and ${\beta }_{a,0,x}$ be values of the parameters of the Beta prior placed on $w_{a,x}$, then an upper bound for ${\alpha }_{a,T,x},T\ge 1$ is simply (B1) $${\alpha }_{a,T,x}\le {\alpha }_{a,0,x}+\left|{\tau }_{a,T}\right|$$(B1) since ${\alpha }_{a,T,x}$ can only increase by at most one at times when when $a\in A_t$ and is unchanging at other times.

For a lower bound on $\mathbb{E}\left[{\beta }_{a,T,x}\right]$ we consider only times when $a\in A_t,q_{t,x}=1$ and y_t = 0. Then y_t = 0 guarantees that arm a is considered by the user and $q_{t,x}=1$ means the failure to click can be attributed to $w_{a,x}$. Hence, for $t\ge 1$, (B2) $${\beta }_{a,t+1,x}\left|\right(q_{t,x}=1,y_t=0,a\in A_t,{\beta }_{a,t,x})={\beta }_{a,t,x}+1.$$(B2)

At all times ${\beta }_{a,t+1,x}\ge {\beta }_{a,t,x}$ since the β parameters cannot decrease. For PCM, $$\mathrm{Pr}(y_t=0|q_{t,x}=1,A_t,{\mathbf{w}}_{A_t})=\prod _{b\in A_t}(1-w_{b,x})$$ which is no larger than the corresponding probability for TCM. The probability that y_t = 0 can therefore be bounded below. Let $w^{*}={\max }_{b\in \mathcal{A},\mathrm{x\hspace{0.17em}}}{w}_{b,x}$ and $q^{*}={\min }_{t,\mathrm{x\hspace{0.5em}}}\mathrm{Pr}(q_{t,x}=1)$ then for any $A_t\subset \mathcal{A}$, (B3) $$\mathrm{Pr}(y_t=0|A_t,{\mathbf{w}}_{\mathcal{A}})\ge q^{*}{(1-w^{*})}^m.$$(B3)

We can now give a lower bound on $\mathbb{E}\left[{\beta }_{a,T,x}|I_1\right]$ where the expectation is joint over all ${\mathbf{q}}_t$, y_t, $m_t^{*}$ for $t=1,\dots ,T$, and I₁ is just the priors for W. Using (B2) and (B3), we have at any time T, (B4) $$\begin{array}{l}\mathbb{E}\left[{\beta }_{a,T,x}\right|I_1]\ge {\beta }_{a,0,x}+\sum _{t\in {\tau }_{a,T}}[\mathrm{Pr}(q_{t,x}=1)\mathrm{Pr}(y_t=0|q_{t,x}=1,a\in A_t,{\mathbf{w}}_{A_t}\left)\right]\\ \ge \left|{\tau }_{a,T}\right|q^{*}{(1-w^{*})}^m.\end{array}$$(B4)

Let $\eta =q^{*}{(1-w^{*})}^m$ and note that $\eta >0$ since $w^{*}<1$ by the problem definition and $q^{*}>0$ by the assumption given in the statement of the Lemma. Combining (B1) and (B4) gives, for any ${\tau }_{a,T}$, $$\begin{array}{c}\mathbb{E}\left[\frac{{\beta }_{a,T,x}}{{\alpha }_{a,T,x}}|I_1\right]\ge \frac{1}{{\alpha }_{a,0,x}+\left|{\tau }_{a,T}\right|}\mathbb{E}\left[{\beta }_{a,T,x}|I_1\right]\\ \ge \frac{\left|{\tau }_{a,T}\right|\eta }{{\alpha }_{a,0,x}+\left|{\tau }_{a,T}\right|}\end{array}$$ and so by the strong law of large numbers, for sufficiently large $\left|{\tau }_{a,T}\right|$ and conditional on I₁, (B5) $$\frac{{\beta }_{a,T,x}}{{\alpha }_{a,T,x}}\ge \frac{\left|{\tau }_{a,T}\right|\eta }{{\alpha }_{a,0,x}+\left|{\tau }_{a,T}\right|}\to \eta .$$(B5)

Note that $${\mu }_{a,T,x}=\frac{{\alpha }_{a,T,x}}{{\alpha }_{a,T,x}+{\beta }_{a,T,x}}=\frac{1}{1+\frac{{\beta }_{a,T,x}}{{\alpha }_{a,T,x}}},$$ and so from (B5), (B6) $$\mathrm{Pr}\left({\mu }_{a,T,x}\le \frac{1}{1+\eta -{\delta }_1}\right)\to 1\hspace{1em} \text{as} \hspace{1em}\left|{\tau }_{a,T}\right|\to \infty$$(B6) for any δ₁ such that $\eta >{\delta }_1>0$.

Then, using the variance of a Beta distribution and (B4) we have $$\begin{array}{l}Var\left(W_{a,T,x}\right)=\frac{{\alpha }_{a,T,x}{\beta }_{a,T,x}}{{({\alpha }_{a,T,x}+{\beta }_{a,T,x})}^2({\alpha }_{a,T,x}+{\beta }_{a,T,x}+1)}\\ <\frac{{({\alpha }_{a,T,x}+{\beta }_{a,T,x})}^2}{{({\alpha }_{a,T,x}+{\beta }_{a,T,x})}^2({\alpha }_{a,T,x}+{\beta }_{a,T,x}+1)}\\ =\frac{1}{({\alpha }_{a,T,x}+{\beta }_{a,T,x}+1)}\to 0\hspace{1em} \text{as} \hspace{1em}\left|{\tau }_{a,T}\right|\to \infty ,\end{array}$$ and so for any ${\delta }_2>0$ the sampled ${\tilde{w}}_{a,T,x}\sim W_{a,T,x}$ satisfy (B7) $$\mathrm{Pr}\left({\tilde{w}}_{a,T,x}\le {\mu }_{a,T,x}+{\delta }_2\right)\to 1\hspace{1em} \text{as} \hspace{1em}\left|{\tau }_{a,T}\right|\to \infty .$$(B7)

By definition $R^{TS}(a,{\mathbf{W}}_{a,t},{\mathbf{q}}_t|I_t)={\sum }_{x=1}^n(q_{t,x}{\tilde{w}}_{a,t,x})\le {\max }_{\mathrm{x\hspace{0.17em}}}{\tilde{w}}_{a,t,x}$ where ${\tilde{w}}_{a,t,x}\sim W_{a,t,x}$. Therefore, to complete the proof it is sufficient that $\mathrm{Pr}({\tilde{w}}_{a,T,x}<1/(1+\eta -{\delta }_1)+{\delta }_2)\to 1$ as $\left|{\tau }_{a,T}\right|\to \infty$ for all $a\in \mathcal{A},x=1,\dots n$ and any δ₁, δ₂ such that $\eta >{\delta }_1>0$ and ${\delta }_2>0$, which follows from (B6) and (B7). □

Appendix C: Proof of Theorem 5.1

The proof will assume that there is a non-empty set of arms ${\mathcal{A}}_F\subset \mathcal{A}$ whose members are sampled finitely often as $t\to \infty$ and show that this leads to a contradiction. Under this assumption $\sum _{b\in {\mathcal{A}}_F}\left|{\tau }_{b,\infty }\right|<\infty$ and so there exists a finite time $M={\max }_{b\in {\mathcal{A}}_F}{\tau }_{b,t}$ even as $t\to \infty$.

Let ${\mathcal{A}}_I=\mathcal{A}\setminus {\mathcal{A}}_F$ be the set of arms sampled infinitely often (which must be non-empty). Let $w^{*}={\max }_{a\in \mathcal{A},x}{w}_{a,x}$ and $\eta =q^{*}{(1-w^{*})}^m$ as in the proof of Lemma B.1. Note that $\eta >0$ since $w^{*}<1$ by the problem definition and $q^{*}>0$ by the given condition. Then fix some $0<{\delta }_1<\eta$ and $0<{\delta }_2<1-1/(1+\eta -{\delta }_1)$. Then by Lemma B.1 for all $a\in {\mathcal{A}}_I$, $$\mathrm{Pr}\left(R^{TS}(a,{\mathbf{W}}_{a,t},{\mathbf{q}}_t)\le \frac{1}{1+\eta -{\delta }_1}+{\delta }_2\right)\to 1 \text{as} t\to \infty .$$

So there exists a finite random time T > M such that (C1) $$\mathrm{Pr}\left(R^{TS}(a,{\mathbf{W}}_{a,t},{\mathbf{q}}_t)\le \frac{1}{1+\eta -{\delta }_1}+{\delta }_2\right)>1-{\delta }_2 \text{for} t>T,\hspace{0.5em}\forall a\in {\mathcal{A}}_I.$$(C1)

Let $ϵ={\min }_{b\in {\mathcal{A}}_F}[\mathrm{Pr}(R^{TS}(b,{\mathbf{W}}_{b,T},{\mathbf{q}}_T|I_T)>1/(1+\eta -{\delta }_1)+{\delta }_2)]$. Then for all t > T, $b\in {\mathcal{A}}_F$ we have (C2) $$\mathrm{Pr}\left(R^{TS}(b,{\mathbf{W}}_{b,t},{\mathbf{q}}_t|I_t)>\frac{1}{1+\eta -{\delta }_1}+{\delta }_2\right)\ge ϵ,$$(C2) since no arm in ${\mathcal{A}}_F$ is selected at times t > T > M and so ${\mathbf{W}}_{b,t}$ is unchanged over these times. We know that $ϵ>0$ since $\mathrm{Pr}({\tilde{w}}_{b,T,x}>1/(1+\eta +{\delta }_1)+{\delta }_2)>0$ for all b, x because $1/(1+\eta -{\delta }_1)+{\delta }_2<1$ and $W_{b,T,x}$ is a Beta distribution with support (0, 1).

Combining (C1) and (C2), (C3) $$\mathrm{Pr}\left[R^{TS}\right(b,{\mathbf{W}}_{b,t},{\mathbf{q}}_t\left|I_t\right)>R^{TS}(a,{\mathbf{W}}_{a,t},{\mathbf{q}}_t|I_t),\forall a\in A]>ϵ(1-{\delta }_2)$$(C3) for all t > T. Therefore $$\sum _{t=T}^{\infty }\mathrm{Pr}(b\in A_t \text{for} \text{some} b\in {\mathcal{A}}_F)>\sum _{t=T}^{\infty }ϵ{(1-{\delta }_2)}^{\left|{\mathcal{A}}_I\right|}=\infty .$$

Using the Extended Borel–Cantelli Lemma (Corollary 5.29 of Breiman, 1992) it follows that $\sum _{b\in {\mathcal{A}}_F}\left|{\tau }_{b,\infty }\right|=\infty$ which contradicts the assumption that $\left|{\tau }_{b,\infty }\right|$ is finite for all $b\in {\mathcal{A}}_F$. Therefore some arm in ${\mathcal{A}}_F$ is selected infinitely often and since ${\mathcal{A}}_F$ was of arbitrary size it follows that ${\mathcal{A}}_F=\varnothing$.