\section{Introduction and Motivation}
\label {sec:intro}
\input {sections/introduction.tex}

\section{Map Entry: Is Bandit the Right Formulation?}
\label {sec:entry}
\input {sections/map_entry.tex}

\section{Navigation by Reward}
\label {sec:reward}
\input {sections/navigation_by_reward.tex}

\section{Navigation by Action}
\label {sec:action}
\input {sections/navigation_by_action.tex}

\section{Other Topics}
\label {sec:others}
\input {sections/other_topics.tex}

\section{Conclusions}
\label {sec:conlcusions}
\input {sections/conclusions.tex}





\subsection{Problem Formulation}
We model sequential decision making in linear flow as a MDP. Let $D$ be number of the pages that content recommendation is needed. For each page $i$, there are $N_{i}$ content candidates that we can choose from. The selected content can be denoted as $a_{i,n_i}$ where $n_i \in \{ 1, 2, \cdots, N_{i} \}$. For simplicity, we will denote the content shown on page $i$ as $a_{i}$ unless the notation $a_{i,n_i}$ is needed to distinguish between different content for page $i$. The flow starts with state $S_{1, X}$ where $X$ is customer feature vector. After action $a_{i}$ is selected to show to customer with features $X$ on page $i$, there are two possible states: $S_{i+1, X, a_{i}}$ and $S_{Exit}$. The only exception is for the last page, page $D$, the two possible states after action $a_{D}$ are: $S_{End}$ and $S_{Exit}$. $S_{i+1, X, a_{i}}$ means customers move forward in the process to the next page after seeing $a_{i}$. $S_{Exit}$ means customers drop from the process without reaching the end and $S_{End}$ means customers reached the end. We denote $R_{i}$ and $G_{i}$ as short--term and long--term rewards after action ${a_{i}}$ respectively. The goal from a linear flow is to optimize $G_1$.


In Prime cancellation use case, $D$ is $3$ and $a_{i}$ are marketing content designed to retain customers. Customers are at $S_{1, X}$ after they click on the End Membership button. We may have Prime benefits usage and tenure features in $X$. We may also include the upstream channel that customers landed from in $X$. Customers get to $S_{Exit}$ if they drop from the cancellation process at any page leading to $R_{i} = 1$. Customers are in $S_{i+1, X, a_{i}}$ if they move on in the process after marketing content $a_{i}$. The short-term reward is 0 from entering $S_{i+1, X, a_{i}}$. $S_{End}$ is another termination state other than $S_{Exit}$. Customers reach this state if they cancel their membership after seeing content on the last page. This leads to $R_{D} = 0$.  

\subsection{Transition Probability Matrix Modeling}
We use contextual Bandit to model and update transition probability matrix. As our reward are binary and there can be only two outcomes per action, we use Bayesian linear Probit regression \cite{BLIP} to model our reward. The transition probability is formulated through a Probit link function. After showing page $i$, the probability of customers moving forward in the process and dropping from the process is formulated as in Equations \ref{eq:1} and \ref{eq:2} respectively. By using this formulation, we model only interdependence between two successive pages. For page 1, $a_{i-1}$ is dropped from the subscripts but the rest of the equations remain the same.

\begin{equation}
P(S_{t+1} = S_{i+1, X, a_{i}}|S_{t} = S_{i, X, a_{i-1}}, a_{t} = a_{i}) = \Phi(-1 * \frac{B_{X, a_{i-1}, a_{i}}^TW_{i}}{\beta}) \label{eq:1}
\end{equation}


\begin{equation}
P(S_{t+1} = S_{Exit}|S_{t} = S_{i, X, a_{i-1}}, a_{t} = a_{i}) = \Phi(\frac{B_{X, a_{i-1}, a_{i}}^TW_{i}}{\beta}) \label{eq:2}
\end{equation}

In the formula, $\Phi$ is cumulative distribution function for standard normal distribution. $\beta$ is a scaling hyperparameter. $W_{i}$ are the weights quantifying feature contributions to the utility function. $B_{X, a_{i-1}, a_{i}}$ is the final vector that we will learn weights for and formed by combining $X$, $a_{i-1}$ and $a_{i}$ (usually with interaction terms). $B_{X, a_{i-1}, a_{i}}$ is the reason why we can easily model content incompatibility. To explain this, let's first assume we have one feature $x$ for $X$, $a_{i-1}$ has two candidates: $a_{i-1,1}$ and $a_{i-1,2}$, and $a_{i}$ has three candidates: $a_{i,1}$, $a_{i,2}$ and $a_{i,3}$. We know $a_{i,3}$ cannot be shown if $a_{i-1,1}$ is shown to customers. We may set $B_{a_{i-1}, a_{i}}$ as in Equation \ref{eq:3} where we have $1$ for intercept and contextual feature interacting with action terms. We recognize content incompability between $a_{i-1,1}$ and $a_{i,3}$ by simply omitting interaction term $x \cdot a_{i-1,1} \cdot a_{i,3}$ in the equation. In addition, we can interpret interdependence strength between pages by checking the weights for the interaction terms across pages.


\begin{equation}
  \begin{split}
    B_{X, a_{i-1}, a_{i}}^T &= (1, x \cdot a_{i,1}, x \cdot a_{i,2}, x \cdot a_{i,3}, \\
    &a_{i-1,1} \cdot a_{i,1}, a_{i-1,1} \cdot a_{i,2}, \\
    &a_{i-1,2} \cdot a_{i,1}, a_{i-1,2} \cdot a_{i,2}, a_{i-1,2} \cdot a_{i,3}) \label{eq:3} \\
  \end{split}
\end{equation}

We assume the weights $W_{i}$ follow Normal distribution parameterized by a mean vector $\boldsymbol{\mu}_{W_i}$ and variance vector $\boldsymbol{\nu}_{W_i}$. We update the distribution from prior to posteriror by enforcing Normal distribution as the distribution type and obtaining the distribution parameters by minimizing KL-divergence from the approximate normal distribution and the exact distribution \cite{BLIP}.  

\subsection{RL Policy and Policy Updating}
We propose Algorithm \ref{alg:seqTS} \textit{MDP with Bandits} to solve the formulated MDP. $\mathscr{D}_d$ denotes the dataset for updating contextual Bandit for Page $d$. $k$ denotes the $k^{th}$ impression. $a_i^*(a_{i-1})$ denotes the optimal action for page $i$ given content on page $i-1$. The complexity of the algorithm is $O(DN^2K)$ assuming number of content on each page is $N$ for discussion simplicity. For each observation, we sample weights from their posterior distribution using TS for calculating transition probability matrix. We then employ exact DP to allocate the optimal series of content to show on each page given the weights. Per reward signal availability, we update the weights distributions and the loop repeats. If we get the feedback signal in batches, the algorithm alters on Lines 11 and 12 where we would have the updates at batch level instead of observation level.

\begin{algorithm}
\begin{algorithmic}[1]
\State Init $\mathscr{D}_1 = \mathscr{D}_2 = \cdots = \mathscr{D}_D = \oldemptyset$
\For{$k = 1,\cdots, K$}
    \State Receive context $x_k$ and Initiate $\E[G|a_D] = 0$
    \State Sample $W_{1}, \cdots, W_{D}$ from the posterior $P(W_1|\mathscr{D}_1),\cdots, P(W_D|\mathscr{D}_D)$ \algorithmiccomment{TS}
    \For{$i = D, D - 1, \cdots, 2$} \algorithmiccomment{Line 5 - 9: Exact DP}
        \For{ $a_{i - 1}$ in content pool of page $i - 1$}: 
            \begin{gather}    \label{eq:eq2}
            \begin{split}
                a_i^*(a_{i-1}) = \underset{a_{i}}{\argmax} \big\{ \E[R|a_{i}, a_{i-1}, x_k; W_{i}] +& \\
                (1 - \E[R|a_{i}, a_{i-1}, x_k; W_{i}]) * \E[G|a_{i}] \big\}&
            \end{split}
            \end{gather}
            \begin{gather}    \label{eq:eq3}
            \begin{split}
                \E[G|a_{i - 1}] = \E[R|a_i^*(a_{i-1}), a_{i-1}, x_k; W_{i}] + &\\
                (1 - \E[R|a_i^*(a_{i-1}), a_{i-1}, x_k; W_{i}]) * \E[G|a_{i}]&
            \end{split}
            \end{gather}
        \EndFor
    \EndFor
\State $a_1^* = \underset{a_{1}}{\argmax} \big\{ \E[R|a_{1}, x_k; W_1] + (1-E[R|a_{1}, x_k; W_1])\E[G|a_{1}]\big\} $
\State Display layout $\{a_1^*,a_2^*(a_1^*),\cdots, a_{D}^*(a_{D-1}^*)\}$ and observe reward $R_{1,k}, \cdots, R_{D,k}$
\State Update $\mathscr{D}_1 = \mathscr{D}_1 \cup (x_{k}, a_{1k}, R_{1k})$ and Update $\boldsymbol{\mu}_{W_1}$, $\boldsymbol{\nu}_{W_1}$ \algorithmiccomment{BLIP Updating \cite{BLIP}}
\State Update $\mathscr{D}_i = \mathscr{D}_i \cup (x_{k}, a_{ik}, a_{i-1,k}, R_{i,k})$ and Update $\boldsymbol{\mu}_{W_i}$, $\boldsymbol{\nu}_{W_i}$ for $i\in \{2,3,\cdots,D\}$ if $a_{ik}$ was presented
\EndFor
\end{algorithmic}
\caption{MDP with Bandits}
\label{alg:seqTS}
\end{algorithm}




























\subsection{Simulated Data}
We generate simulation data assuming Probit link function between short-term reward $R_{i}$ and $B_{X, a_{i-1}, a_{i}}^TW_{i}$ based on equations \ref{eq:1} and \ref{eq:2}, with $\beta$ set as $1 + \alpha_1 + \alpha_c + \alpha_2$ and the linear model forms for $B_{X, a_{i-1}, a_{i}}^TW_{i}$ specified as in equation \ref{eq:sim_first} for first page and equation \ref{eq:sim} for the other pages. Similar to \cite{MVT}, we use the $\alpha_1$, $\alpha_c$ and $\alpha_2$ to separately control the importance of content to recommend on the current page, content already shown on the previus page, and the interaction between them. For each simulation run, the ground truth weights $W_i$ are sampled independently from a normal distribution with mean $0$ and variance $1$ except for $w_i^0$. Mean for $w_i^0$ is set as $\Phi^{-1}(x)\beta$ where $x$ reflects the average success rate. With a larger value for $\alpha_2$, interdependence across pages is set stronger.

\begin{equation}
B_{X, a_{1}}^TW_{1} = w^0_1 + \alpha_1 \sum_{n_1=1}^{N_1} w_{n_1}^1 a_{1,n_1} + \alpha_1 \sum_{x} w_{x}^1 x \label{eq:sim_first}
\end{equation}

\begin{equation}
	\begin{split}
		B_{X, a_{i-1}, a_{i}}^TW_{i} &= w^0_i + \alpha_1 \sum_{n_i=1}^{N_i} w_{n_i}^1 a_{i,n_i} + \alpha_1 \sum_{x} w_{x}^1 x + \\
    &\alpha_c \sum_{n_{i-1}=1}^{N_{i-1}} w_{n_{i-1}}^c a_{i-1,n_{i-1}} + \\
    &\alpha_2 \sum_{n_i=1}^{N_i} \sum_{n_{i-1}=1}^{N_{i-1}} w_{n_i,n_{i-1}}^2 a_{i,n_i} a_{i-1,n_{i-1}} + \\
    &\alpha_2 \sum_{n_i=1}^{N_i} \sum_{x} w_{n_i,x}^2 a_{i,n_i} x \quad \textrm{for} \quad  i\in 2,\cdots,D \label{eq:sim} \\
	\end{split}
\end{equation}

For each simulation, we sample the actual weights in equations \ref{eq:sim_first} and \ref{eq:sim} once and we calculate the long-term reward of each combination $(a_1, \cdots, a_D)$ as:

\begin{equation}
\E[G|W,a_1,\cdots,a_D] = \E[R_1 + (1 - R_1)R_2 + \cdots + \Pi_{i=1}^{D-1}(1 - R_i)R_D] \label{eq:expected_reward}
\end{equation} 
where $R_i = \Phi(\frac{B_{X,a_{i-1}, a_{i}}^TW_{i}}{\beta}) \quad \textrm{for} \quad  i\in 2,\cdots,D$ and $R_1 = \Phi(\frac{B_{X, a_{1}}^TW_{1}}{\beta})$. 

The series of actions for each algorithm are selected by itself. Given sampled weights and selected actions, empirical rewards ($R$) are sampled from the data generation model. Actual reward $G_k$ is 0 if any $R_k$ is 0. Each simulation was run for $K = 14k$ time steps with updating batch size $1k$ to mimic a 2 week experiment. We ran $100$ simulations and report the averaged performance of each algorithm using batch size normalized cumulative regret:
\begin{equation}
\frac{1}{\# runs}\sum_{j=1}^{\# runs} \frac{1}{batchSize}\sum_{k = 1}^{K} (\E[G|W,a_{1,j}^*, \cdots, a_{D,j}^*] - G_{j,k}) \label{eq:regret}
\end{equation} 

Where $\E[G|W,a_{1,j}^*, \cdots, a_{D,j}^*]$ is the best expected long-term reward for $j^{th}$ run and $G_{j,k}$ is the long-term reward for $i^{th}$ run and $k^{th}$ time step.

\subsection{Simulation Results}

\begin{figure}[tb]
\centering
\begin{minipage}[b]{.48\textwidth}
  \centering
  \includegraphics[width=1.0\textwidth]{darwinStrength=2.png}
  \caption{Example run of algorithms on simulated data with $\alpha_1=1, \alpha_c=1, \alpha_2=2$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
  \label{fig:darwinStrength2}
\end{minipage}%
\hfill
\begin{minipage}[b]{.48\textwidth}
  \centering
  \includegraphics[width=1.0\textwidth]{darwinContext.png}
  \caption{Example run of algorithms on simulated data with $\alpha_1=1, \alpha_c=1, \alpha_2=2$ and 1 categorical feature with 3 categories}
  \label{fig:darwinContext}
\end{minipage}
\end{figure}

\begin{figure}[tb]
\centering
\begin{minipage}[b]{.48\textwidth}
  \centering
  \includegraphics[width=1.0\textwidth]{darwinPage.png}
  \caption{Algorithm performance as number of pages vary. $\alpha_1 = 1, \alpha_2 = 1, \alpha_2 = 2$}
  \label{fig:darwinPage}
\end{minipage}%
\hfill
\begin{minipage}[b]{.48\textwidth}
  \centering
    \includegraphics[width=1.0\textwidth]{darwinStrength.png}
  \caption{Algorithm performance as $\alpha_2$ is varied. $\alpha_1=1, \alpha_c=1$}
  \label{fig:darwinStrength}
\end{minipage}
\end{figure}

We first compare the performance with $\alpha_1=1, \alpha_c=1, \alpha_2=2$ in both non-contextul and contextual use case. In the contextual case, we include $14$ categorical feature with $3$ equally-likely categories. We assume $3$ pages and each page has $3$ content candidates. Results are shown in figures \ref{fig:darwinStrength2} and \ref{fig:darwinContext}. The proposed algorithm converges faster than all the other three. Also, it has the lowest cumulative regret followed by interaction Bandits. This means when there is considerable interdependence across pages, modeling interactions in the transition probability reduces regrets and modeling the process as a MDP instead of separate Bandits further lifts the performance. On the other hand, bandit algorithms with TS generally outperform Q\-learning with $\epsilon$-greedy, given its efficiency in exploration.

We then take a look at the impact of number of pages on performance, shown in figure \ref{fig:darwinPage}. The number of pages varies from $2$ to $6$ and that of content combinations $N^D$ varies from $9$ to $729$. MDP with Bandits consistently outperforms the other three algorithms. The performance advantage over Q-learning shrinks with increasing page number. 


To test the model's sensitivity to interdependence strength, we conduct a set of simulation runs with $\alpha_2$ increasing from 0 to 3 while fixing $\alpha_1$ and $\alpha_c$ at $1$. Results are shown in figure \ref{fig:darwinStrength}. When $\alpha_2$ is $0$, independent bandits algorithm outperforms the other two bandit algorithms as both interaction Bandits and MDP with Bandits require traffic to learn the weights for interaction terms should actually be set as $0$. As $\alpha_2$ increases, MDP with Bandits starts to outperform. As Q-learning directly learns the Q function by Bellman equation, interaction strength has minor influence to its performance. Overall, the performance for MDP with Bandits is consistently better than all other algorithms when interaction strength is greater than 1.





\subsection{Feature Engineering}
In many applications, we use features to deal with large context or action sets more efficiently.
The expected reward $r$ can be written as a function of action features $\boldsymbol{{\phi}_a}$ and contextual features $\boldsymbol{{\phi}_x}$: $E[r] = f(\boldsymbol{{\phi}_a}, \boldsymbol{{\phi}_x})$.
Feature engineering in Bandit involves selection/pre-processing of $\boldsymbol{{\phi}_a}$ and $\boldsymbol{{\phi}_x}$ and their interaction terms. Linear Bandits are the most studied in the literature where $E[r]$ is assumed to be linear in the features. To model non-linearity especially when the size(s) of $\boldsymbol{{\phi}_a}$ or/and $\boldsymbol{{\phi}_x}$ is large, we can learn lower-dimension embeddings from the raw features ($\boldsymbol{{\phi}_a}$ or/and $\boldsymbol{{\phi}_x}$) and put the embeddings in the reward function instead \cite{Lin_adaptive_2020, zahavy2019deep}. Embedding generation techniques for supervised learning generally apply to Bandits~\cite{He_tree_2014}. Another way to relax the linear-reward assumption is to use non-linear Bandits where reward function becomes non-linear in feature vectors~\cite[e.g.,][]{zhou2020neural}. 

\subsection{Offline Policy Evaluation}
Testing a Bandit policy in real user traffic is often expensive, and poses risks on user experiences. It is common to evaluate a new policy offline before deploying it. A key challenge in offline policy evaluation is that we do not know how users would have reacted to actions different from the one in the log data, since the data only have rewards for selected actions. This \emph{counterfactual} nature makes Bandit offline evaluation similar to causal inference where we want to infer the average reward $E_{\pi}[r]$ (the causal effect) if policy $\pi$ is used to choose actions.
There exist effective approaches to evaluating a stationary policy, including simulation~\cite{Genie19}, inverse propensity scoring \cite{Bottou_counterfactual_2013, Strehl_loggeddata_2010}, doubly robust evaluation \cite{dudik2011doubly}, and self-normalized inverse propensity estimators \cite{Swaminathan_snip_2015}. 
Typically, offline evaluation becomes more challenging with a larger action set.
For a slate Bandit, pseudoinverse estimator is available to account for position bias \cite{Swaminathan_slate_2017}. Offline evaluation for non-stationary Bandits remains challenging \cite{Li_offline_2011,dudik2012sampleefficient}, with opportunities for further research.

\subsection{Best-arm Identification}
In some bandit applications, our goal is not to maximize reward during an experiment, but to identify the best action (e.g., best marketing campaign strategy) at the end of the experiment. This problem, known as best-arm identification \cite{kazerouni2019best, soare2014bestarm, Bubeck_pure_2010}, shares the same goal as conventional A/B/N testing~\cite{Kohavi20}, but can be statistically more efficient by adaptively selecting actions during an experiment.