Leveraging (Biased) Information: Multi-armed Bandits with Offline Data

Multi-armed bandit problem (MAB) is a classical model in sequential decision-making. In traditional models, online learning is initialized with no historical dataset. However, in many real world scenarios, historical datasets related to the underlying model exist before online learning begins. Those datasets could be beneficial to online learning. For instance, when a company launch a new product in Singapore, past sales data in the US could be of relevance. This prompts an intriguing question: Can we develop an approach that effectively utilizes offline data, and subsequently learns under bandit feedback? Such approaches carry significant allure, as they potentially reduce the amount of exploration in the learning process. Nevertheless, it is too strong and impractical to assume that the historical dataset and the online model follow the same probability distribution, given the ubiquity of distributional shifts. Therefore, it is desirable to design an adaptive policy that reaps the benefit of offline data if they closely match the online model, while judiciously ignores the offline data and learns from scratch otherwise.

Motivated by the above discussions, we consider a stochastic multi-armed bandit model with possibly biased offline dataset. The entire event horizon consists of a warm-start phase, followed by an online phase whereby decision making occurs. During the warm-start phase, the DM receives an offline dataset, consisting of samples governed by a latent probabiltiy distribution $P^{\text{(off)}}$. The subsequent online phase is the same as standard multi-armed bandit model, except that the offline dataset can be incorporated in decision making. The random online rewards are governed by another latent probabiltiy distribution $P^{\text{(on)}}$. The DM aims to maximize the total cumulative reward earned, or equivalently minimize the regret, during the online phase.

Intuitively, when $P^{\text{(off)}}$, $P^{\text{(on)}}$ are “far apart”, the DM should conduct online learning from scratch and ignore the offline dataset. For example, the vanilla UCB policy by (Auer et al., 2002) incurs expected regret at most

where $T$ is the length of online phase, and $\Delta(a)\geq 0$ is the difference between the expected reward of an optimal arm and arm $a$ (also see Section 2). The bound (1) holds for all $P^{\text{(off)}}$, $P^{\text{(on)}}$. In contrary, when $P^{\text{(off)}}$, $P^{\text{(on)}}$ are “sufficiently close”, the DM should incorporate the offline data into online learning and avoid unnecessary exploration. For example, when $P^{\text{(off)}}=P^{\text{(on)}}$, HUCB1 (Shivaswamy & Joachims, 2012) and MonUCB (Banerjee et al., 2022) incur expected regret at most

where $T_{\text{S}}(a)$ is the number of offline samples on arm $a$. (2) is a better regret bound than (1). However, (2) only holds when $P^{\text{(off)}}=P^{\text{(on)}}$. The above inspires the following question:

(Q) Can the DM outperform the vanilla UCB, i.e. achieves a better regret bound than (1) when $P^{\text{(off)}}=P^{\text{(on)}}$, while retains the regret bound (1) for general $P^{\text{(off)}},P^{\text{(on)}}$?

The answer to (Q) turns out to be somewhat mixed. Our novel contributions shed light on (Q) as follows:

Impossibility Result. We show in Section 3 that no non-anticipatory policy can achieve the aim in (Q). Even with an offline dataset, no non-anticipatory policy can outperform the vanilla UCB without any additional knowledge or restriction on the difference between $P^{\text{(off)}},P^{\text{(on)}}$.

Algorithm design and analysis. To bypass the impossibility result, we endow the DM with an auxiliary information dubbed valid bias bound $V$, which is an information additional to the offline dataset. The bound $V$ serves as an upper bound on the difference between $P^{\text{(off)}}$ and $P^{\text{(on)}}$. We propose the MIN-UCB policy, which achieves a strictly better regret bound than (1) when $P^{\text{(off)}},P^{\text{(on)}}$ are “sufficiently close”. In particular, our regret bound reduces to (2) if the DM knows $P^{\text{(off)}}=P^{\text{(on)}}$. We provide both instance dependent and independent regret upper bounds on MIN-UCB, and we show their tightness by providing the corresponding regret lower bounds. Our analysis also pins down the precise meaning of “far apart” and “sufficientlly close” in the above discussion. The design and analysis of MIN-UCB are provided in Section 4.

In particular, when $P^{\text{(off)}}=P^{\text{(on)}}$, our analysis provide two novel contributions. Firstly, we establish the tightness of the instance dependent bound (2). Secondly, we establish a pair of instance independent regret upper and lower bounds, which match each other up to a logarithmic factor. MIN-UCB is proved to achieve the upper bound when $P^{\text{(off)}}=P^{\text{(on)}}$. Both the upper and lower bounds are novel in the literature, and we show that the optimal regret bound involves the optimum of a novel linear program.

We consider a stochastic $K$-armed bandit model with possibly biased offline data. Denote ${\cal A}=\{1,\ldots,K\}$ as the set of $K$ arms. The event horizon consists of a warm-start phase, then an online phase. During the warm-start phase, the DM receive a collection of $T_{\text{S}}(a)\in\mathbb{Z}_{\geq 0}$ i.i.d. samples, denoted $S(a)=\{X_{s}(a)\}^{T_{\text{S}}(a)}_{s=1}$, for each $a\in{\cal A}$. We postulate that $X_{1}(a),\ldots,X_{T_{\text{S}}(a)}(a)\sim P^{\text{(off)}}_{a}$, the offline reward distribution on arm $a$.

The subsequent online phase consists of $T$ time steps. For time steps $t=1,\ldots,T$, the DM chooses an arm $A_{t}\in{\cal A}$ to pull, which gives the DM a random reward $R_{t}$. Pulling arm $a$ in the online phase generates a random reward $R(a)\sim P^{\text{(on)}}_{a}$, dubbed the online reward distribution on arm $a$. We emphasize that $P^{\text{(on)}}=\{P^{\text{(on)}}_{a}\}_{a\in{\cal A}}$ needs not be the same as $P^{\text{(off)}}=\{P^{\text{(off)}}_{a}\}_{a\in{\cal A}}$. Finally, the DM proceeds to time step $t+1$, or terminates when $t=T$.

The DM chooses arms $A_{1},\ldots,A_{T}$ with a non-anticipatory policy $\pi=\{\pi_{t}\}^{\infty}_{t=1}$. The function $\pi_{t}$ maps the observations $H_{t-1}=(S=\{S(a)\}_{a\in{\cal A}},\{(A_{s}.R_{s})\}^{t-1}_{s=1})$ collected at the end of $t-1$, to an element in $\{x\in\mathbb{R}^{K}_{\geq 0}:\sum_{a\in{\cal A}}x_{a}=1\}$. The quantity $\pi_{t}(a~{}|~{}H_{t-1})\in[0,1]$ is the probability of $A_{t}=a$, conditioned on $H_{t-1}$ under policy $\pi$. While our proposed algorithms are deterministic, i.e. $\pi_{t}(a~{}|~{}H_{t-1})\in\{0,1\}$ always, we allow randomized policies in our regret lower bound results. The policy $\pi$ could utilize $S$, which provides a potentially biased estimate to the online model since we allow $P^{\text{(on)}}\neq P^{\text{(off)}}$.

Altogether, the underlying instance $I$ is specified by the tuple $({\cal A},\{T_{\text{S}}(a)\}_{a\in{\cal A}},P,T)$, where $P=(P^{\text{(off)}},P^{\text{(on)}})$. The DM only knows ${\cal A}$ and $S$, but not $P$ and $T$, at the start of the online phase. For every $a\in{\cal A}$, we assume that both $P^{\text{(off)}}_{a},P^{\text{(on)}}_{a}$ are 1-subGaussian, which is also known to the DM. For $a\in{\cal A}$, denote $\mu^{\text{(on)}}(a)=\mathbb{E}_{R(a)\sim P^{\text{(on)}}_{a}}[R(a)]$, and $\mu^{\text{(off)}}(a)=\mathbb{E}_{R(a)\sim P^{\text{(off)}}_{a}}[R(a)]$. We do not have any boundedness assumptions on $\mu^{\text{(on)}}(a),\mu^{\text{(off)}}(a)$.

The DM aims to maximize the total reward earned in the online phase. We quantify the performance guarantee of the DM’s non-anticipatory policy by its regret. Define $\mu_{*}^{\text{(on)}}=\max_{a\in{\cal A}}\mu^{\text{(on)}}(a)$, and denote $\Delta(a)=\mu^{\text{(on)}}_{*}-\mu^{\text{(on)}}(a)$ for each $a\in{\cal A}$. The DM aims to design a non-anticipatory policy $\pi$ minimize the regret

despite the uncertainty on $P$. While (3) involves only $\mu^{\text{(on)}}$ but not $\mu^{\text{(off)}}$, the choice of $A_{t}$ is influenced by both the offline data $S$ and the online data $\{A_{s},R_{s}\}^{t-1}_{s=1}$.

As mentioned in the introduction and detailed in the forthcoming Section 3, the DM cannot outperform the vanilla UCB policy with a non-anticipatory policy. Rather, the DM requires information additional to the offline dataset and a carefully designed policy. We consider the following auxiliary input in our algorithm design.

Auxiliary input: valid bias bound. We say that $V=\{V(a)\}_{a\in{K}}\in(\mathbb{R}\cup\{\infty\})^{|\mathcal{A}|}$ is a valid bias bound on an instance $I$ if

In our forthcoming policy MIN-UCB, the DM is endowed the auxiliary input $V$ in addition to the offline dataset $S$ before the online phase begins. The quantity $V(a)$ serves as an upper bound on the amount of distributional shift from $P^{\text{(off)}}_{a}$ to $P^{\text{(on)}}_{a}$. The condition (4) always holds in the trivial case of $V(a)=\infty$, which is when the DM has no additional knowledge. By contrast, when $V(a)\neq\infty$, the DM has a non-trivial knowledge on the difference $|\mu^{\text{(off)}}(a)-\mu^{\text{(on)}}(a)|$.

The knowledge on an upper bound such as $V$ is in line with the model assumptions in research works on learning under distributional shift. Similar upper bounds are assumed in the contexts of supervised learning (Crammer et al., 2008), stochastic optimization (Besbes et al., 2022), offline policy learning on contextual bandits (Si et al., 2023), multi-task bandit learning (Wang et al., 2021), for example. Methodologies for constructing such upper bounds are provided in some literature. For instance, (Blanchet et al., 2019) designs an approach based on several machine learning estimators, such as LASSO. (Si et al., 2023) provides some managerial insights on how to construct them empirically. (Chen et al., 2022) constructs them through cross-validation, and implement it in a case study.

We illustrate the impossibility result with two instances $I_{P},I_{Q}$. The instances $I_{P},I_{Q}$ share the same ${\cal A}=\{1,2\},\{T_{\text{S}}(a)\}_{a\in{\cal A}}$ and $T$. However, $I_{P},I_{Q}$ differ in their respective reward distributions $P$, $Q$, and $I_{P},I_{Q}$ have different optimal arms. Consider a fixed but arbitrary $\beta\in(0,1/2)$. Instance $I_{P}$ has well-aligned reward distributions $P^{\text{(off)}}=P^{\text{(on)}}$, where

Note that $\Delta(2)=T^{-\beta}$. In $I_{P}$, an offline dataset provides useful hints on arm 1 being optimal. For example, given $T_{\text{S}}(1)=T_{\text{S}}(2)\geq 128(T^{2\beta}-T^{2\beta-\epsilon})\log T$ where $\epsilon\in(0,\beta)$, the existing policies H-UCB and MonUCB achieve an expected regret (see Equation (2)) at most

which strictly outperforms the vanilla UCB policy that incurs expected regret $O(\log T/\Delta(2))=O(T^{\beta}\log T)$. Despite the apparent improvement, the following claim shows that any non-anticipatory policy (not just H-UCB or MonUCB) that outperforms the vanilla UCB on $I_{P}$ would incur a larger regret than the vanilla UCB on a suitably chosen $I_{Q}$.

Proposition 3.1 is proved in Appendix section C.2. We first remark on $I_{Q}$. Different from $I_{P}$, arm 2 is the optimal arm in $I_{Q}$. Thus, the offline data from $Q^{\text{(off)}}$ provides the misleading information that arm 1 has a higher expected reward. In addition, note that $Q^{\text{(off)}}=P^{\text{(off)}}$, so the offline datasets in instances $I_{P},I_{Q}$ are identically distributed. The proposition suggests that no non-anticipatory policy can simultaneously (i) establish that $S$ is useful for online learning in $I_{P}$ to improve upon the UCB policy, (ii) establish that $S$ is to be disregarded for online learning in $I_{Q}$ to match the UCB policy, negating the short-lived conjecture in (Q).

Lastly, we allow $T_{\text{S}}(1),T_{\text{S}}(2)$ to be arbitrary. In the most informative case of $T_{\text{S}}(1)=T_{\text{S}}(2)=\infty$, meaning that the DM knows $P^{\text{(off)}},Q^{\text{(off)}}$ in $I_{P},I_{Q}$ respectively, the DM still cannot achieve (i, ii) simultaneously. Indeed, the assumed improvement $\mathbb{E}[\text{Reg}_{T}(\pi,P)]\leq CT^{\beta-\epsilon}\log T$ limits the number of pulls on arm 2 in $I_{P}$ during the online phase. We harness this property to construct an upper bound on the KL divergence between on online dynamics on $I_{P}$, $I_{Q}$, which in turns implies the DM cannot differentiate between $I_{P},I_{Q}$ under policy $\pi$. The KL divergence argument utilizes a chain rule (see Appendix C.1) on KL divergence adapted to our setting.

After the impossibility result, we present our MIN-UCB policy in Algorithm 1. MIN-UCB follows the optimism-in-face-of-uncertainty principle. At time $t>K$, MIN-UCB sets $\min\{\text{UCB}_{t}(a),\text{UCB}_{t}^{\text{S}}(a)\}$ as the UCB on $\mu^{\text{(on)}}(a)$. While $\text{UCB}_{t}(a)$ follows (Auer et al., 2002), the construction of $\text{UCB}_{t}^{\text{S}}(a)$ in (6) adheres to the following ideas that incorporates a valid bias bound $V$, the auxiliary input.

In (6), the sample mean $\frac{N_{t}(a)\cdot\hat{R}_{t}(a)+T_{\text{S}}(a)\cdot\hat{X}(a)}{N_{t}(a)+T_{\text{S}}(a)}$ incorporates both online and offline data. Then, we inject optimism by adding $\text{rad}^{\text{S}}(a)$, set in (7). The square-root term in (7) reflects the optimism in view of the randomness of the sample mean. The term $\frac{T_{\text{S}}(a)}{N_{t}(a)+T_{\text{S}}(a)}\cdot V(a)$ in (7) injects optimism to correct the potential bias from the offline dataset. The correction requires the auxiliary input $V$.

Finally, we adopt $\text{UCB}_{t}^{\text{S}}(a)$ as the UCB when the bias bound $V(a)$ is so small and the sample size $T_{\text{S}}(a)$ is so large that $\text{UCB}_{t}(a)>\text{UCB}_{t}^{\text{S}}(a)$. Otherwise, $P^{\text{(off)}}$ is deemed “far away” $P^{\text{(on)}}$, and we follow the vanilla UCB. Our adaptive decisions on whether to incorporate offline data at each time step is different from the vanilla UCB policy that always ignores offline data, or from HUCB and MonUCB that always incorporate all offline data.

Lastly, we remark on $V$. Suppose that the DM possesses no knowledge on $P^{\text{(off)}},P^{\text{(on)}}$ additional to the offline dataset $S$ at the start of the online phase. Then, it is advisable to set $V(a)=\infty$ for all $a$, which specializes MIN-UCB to the vanilla UCB policy. Indeed, the theoretical impossibility result in Section 3 dashes out any hope for adaptively tuning $V$ in MIN-UCB with online data, in order to outperform the vanilla UCB. By contrast, when the DM has a non-trivial upper bound $V(a)$ on $\left|\mu^{\text{(off)}}(a)-\mu^{\text{(on)}}(a)\right|$, we show that can uniformly out-perform the vanilla UCB that direclty ignores the offline data.

We next embark on the analysis on MIN-UCB, by establishing instance dependent regret bounds in Section 4.1 and instance independent regret bounds in Section 4.3. Both sections relies on considering the following events of accurate estimations by $\text{UCB}_{t}(a),\text{UCB}^{\text{S}}_{t}(a)$. For each $t$, define ${\cal E}_{t}=\cap_{a\in{\cal A}}({\cal E}_{t}(a)\cap{\cal E}^{\text{S}}_{t}(a))$, where

While ${\cal E}_{t}(a)$ incorporates estimation error due to stochastic variations, ${\cal E}^{\text{S}}_{t}(a)$ additionally involves the potential bias of the offline data.

The proof of Lemma 4.1 is provided in Appendix B.1.