Best-of-Both-Worlds Linear Contextual Bandits

Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.

46,019 characters · 12 sections · 72 citation commands

Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.

abstractThis study investigates the problem of $K$-armed linear contextual bandits, an instance of the multi-armed bandit problem, under an adversarial corruption. At each round, a decision-maker observes an independent and identically distributed context and then selects an arm based on the context and past observations. After selecting an arm, the decision-maker incurs a loss corresponding to the selected arm. The decision-maker aims to minimize the cumulative loss over the trial. The goal of this study is to develop a strategy that is effective in both stochastic and adversarial environments, with theoretical guarantees. We first formulate the problem by introducing a novel setting of bandits with adversarial corruption, referred to as the contextual adversarial regime with a self-bounding constraint. We assume linear models for the relationship between the loss and the context. Then, we propose a strategy that extends the {\tt RealLinExp3} by Neu2020 and the Follow-The-Regularized-Leader (FTRL). The regret of our proposed algorithm is shown to be upper-bounded by $O\left(\min\left\{\frac{(\log(T))^3}{\Delta_{*}} + \sqrt{\frac{C(\log(T))^3}{\Delta_{*}}},\ \ \sqrt{T}(\log(T))^2\right\}\right)$, where $T \in\mathbb{N}$ is the number of rounds, $\Delta_{*} > 0$ is the constant minimum gap between the best and suboptimal arms for any context, and $C\in[0, T] $ is an adversarial corruption parameter. This regret upper bound implies $O\left(\frac{(\log(T))^3}{\Delta_{*}}\right)$ in a stochastic environment and by $O\left( \sqrt{T}(\log(T))^2\right)$ in an adversarial environment. We refer to our strategy as the {\tt Best-of-Both-Worlds (BoBW) RealFTRL}, due to its theoretical guarantees in both stochastic and adversarial regimes.

Introduction

This study considers minimizing the cumulative regret in the multi-armed bandit (MAB) problem with contextual information. The MAB problem is a formulation of sequential decision-making. In this study, we develop an algorithm that utilizes side information called contextual information. We focus on linear contextual bandits and aim to design an algorithm that performs well in both stochastic and adversarial environments.

In our problem setting of contextual bandits, a decision-maker observes an independent and identically distributed (i.i.d.) context each round, draws an arm accordingly, and incurs a loss associated with the chosen arm. Additionally, we assume linear models between the loss and contexts, which is known as the linear contextual bandit problem. The contextual bandit problem is widely studied in fields such as sequential treatment allocation Tewari2017, personalized recommendations Beygelzimer2011, and online advertising Li2010. Based on these demands, existing studies explore the methods. For example, AbeLong1999 studies linear contextual bandits. Li2021regret provides lower bounds. There are numerous other studies in this field Chen2020efficient,Qin2022robuststochastic.

The settings of linear contextual bandits are divided into stochastic, with fixed contextual and loss distributions, and adversarial environments, with fixed contexts but adversarially chosen losses\footnote{We can define adversarial linear contextual bandits in different ways. For example, there are studies that consider contextual bandits with adversarial contexts and fixed losses Chu2011contextual,AbbasiYadkori2011. On the other hand, several studies address contextual bandits with adversarial contexts and adversarial losses KanadeSteinke2014,HazanKoren2016. This study only focuses on contextual bandits with i.i.d. contexts and adversarial losses, which have been studied by Rakhlin2016 and Syrgkanis2016improved.}. Most existing studies focus on algorithms for either stochastic AbeLong1999,Rusmevichientong2010,Chu2011contextual,AbbasiYadkori2011,Lattimore2017 or adversarial linear contextual bandits Neu2020.

Thus, optimal algorithms typically differ between the stochastic and adversarial environments. However, a best-of-both-worlds framework exists, aiming for algorithms that are competent in both stochastic and adversarial environments BubeckSlivkins2012,SeldinSlivkins2014,AuerChiang2016,SeldinLugosi2017,Zimmert2019,Lee2021achieving. Building on existing work, we propose a best-of-both-worlds algorithm for stochastic and adversarial linear contextual bandits.

Main Contribution

In Section (ref), we first introduce the setting of linear contextual bandits with adversarial corruption by defining the linear contextual adversarial regime with a self-bounding constraint. This setting is a generalization of the adversarial regime with a self-bounding constraint proposed by Zimmert2019. Under this regime, we bridge the stochastic and adversarial environments by an adversarial corruption parameter $C \geq 0$, where $C = 0$ corresponds to a stochastic environment and $C = T$ corresponds to an adversarial environment.

Then, in Section (ref) inspired by the {\tt RealLinEXP3} proposed by Neu2020 for adversarial contexts, our algorithm uses the Follow-the-Regularized-Leader (FTRL) approach to adapt well to the stochastic environment. Our algorithm design also follows existing studies in best-of-both-worlds (BoBW) studies, such as ito2022nearly. We refer to our algorithm as the {\tt BoBW-RealFTRL}.

In Section (ref), we show the upper bound of the {\tt BoBW-RealFTRL} as $O\left(\min\left\{\frac{D}{\Delta_{*}} + \sqrt{\frac{CD}{\Delta_{*}}}, \sqrt{\log(KT)TD}\right\}\right)$, where $D = {K\log(T)}\left(\log(T) + d\log(K)\right)\log(KT)$, $T$ is the number of rounds, $d$ is the dimension of a context, and $K$ is the number of arms, when there exists a constant minimum gap $\Delta_*$ between the conditional expected rewards of the best and suboptimal arms for any context when we consider a stochastic environment. Note that this regret upper bound holds both for stochastic and adversarial environments. When there does not exist such a gap $\Delta_*$, we show that the regret upper bound is given as $O\left(\sqrt{\log(KT)TD}\right)$. Note that this regret upper bound also holds both for stochastic and adversarial environments, as well as the previous upper bound. Combining them, the regret upper bound is $O\left(\min\left\{\frac{D}{\Delta_{*}} + \sqrt{\frac{CD}{\Delta_{*}}}, \sqrt{\log(KT)TD}\right\}\right)$. Note that the regret upper bound under an adversarial environment can hold without any assumption on the existence of $\Delta_{*}$. Our regret upper bound is $O\left(\min\left\{\frac{(\log(T))^3}{\Delta_{*}} + \sqrt{\frac{C(\log(T))^3}{\Delta_{*}}},\ \ \sqrt{T}(\log(T))^2\right\}\right)$ when focusing on the order with respect to $T$. Furthermore, in a stochastic environment, the regret is upper bounded by $O\left(\frac{(\log(T))^3}{\Delta_{*}}\right)$, and in an adversarial environment, the regret is upper bound by $O\left(\sqrt{T}(\log(T))^2\right)$.

In summary, we contribute to the problem of linear contextual bandits by proposing a best-of-both-worlds strategy. Our study enhances the fields of linear contextual bandits and best-of-both-worlds algorithms.

Related Work

In adversarial bandits, the {\tt RealLinExp3}, the algorithm proposed by Neu2020, yields $O\left(\log(T)\sqrt{KdT}\right)$. In Table (ref), we compare our regret upper bounds with the upper bounds of Neu2020.

Regret upper bounds in a stochastic setting are categorized into problem-dependent and problem-independent upper bounds, where the former utilizes some distributional information, such as the gap parameter $\Delta_*$, to bound the regret, while the latter does not. Additionally, problem-dependent regret upper bounds in the stochastic bandits depend on the margin condition characterized by a parameter $\alpha \in [0, +\infty]$ (for the detailed definition, see Remark (ref)). Our case with $\Delta_*$ corresponds to a case with $\alpha = +\infty$. Note that in the adversarial bandits, the margin condition usually does not affect the upper bounds. Dani2008StochasticLO proposes the {\tt ConfidenceBAll}, and AbbasiYadkori2011 proposes {\tt OFUL}. They both present upper bound with and without the assumption of the existence of $\Delta_*$\footnote{Regret upper bounds with the assumption of the existence of $\Delta_*$ are called problem-dependent.}. As mentioned above, the regret upper bound under the assumption of the existence of $\Delta_*$ corresponds to a case with $\alpha = +\infty$ in the margin condition. In contrast, Goldenshluger2013, Wang2018j, and Bastani2020 propose algorithm in a case with $\alpha = 1$. Furthermore, Li2021regret propose the $\ell_1$-{\tt ConfidenceBall} based algorithm whose upper bound tightly depends on unknown $\alpha$.

There are several related studies for linear contextual bandits with adversarial corruption, including Lykouris2018, Gupta2019, zhao2021linear and he2022nearly. Lykouris2018, Gupta2019, and zhao2021linear consider other corruption frameworks characterized by a constant $\widetilde{C} \in [0, T]$, which is different but related to our linear contextual adversarial regime with a self-bounding constraint. he2022nearly uses another constant $\widetilde{C}^\dagger \in [0, T]$ different but closely related to $\widetilde{C}$. For the detailed definitions, see Remark (ref). The essential difference between our and their settings is the existence of the gap $\Delta_*$. Furthermore, while our regret upper bound achieves the polylogarithmic order, those studies show roughly $\sqrt{T}$-order regret upper bounds. he2022nearly presents $\widetilde{O}\left(d\sqrt{K} + d\widetilde{C}^\dagger \right)$ regret under an adversarial corruption characterized by a constant $\widetilde{C}^\dagger > 0$.

table[table omitted — 848 chars of source]

The use of the FTRL approach for adversarial linear bandits is also independently explored by liu2023bypassing to relax the assumption used in Neu2020. In addition to the difference in contributions, while our algorithm utilizes the Shannon entropy in the regularization of the FTRL, liu2023bypassing employs the log-determinant barrier. We expect that combining these two methods will yield a BoBW algorithm with relaxed assumptions, and it is future work.

To establish our BoBW regret bounds, we utilize the self-bounding technique Zimmert2019,wei2018more, which yields poly-logarithmic regret bounds in stochastic environments. This is achieved by integrating regret upper bounds that are contingent on the arm-selection distributions $q_t$, and a lower bound known as self-bound constraints. The $q_t$-dependent regret bounds are obtained using FTRL with a negative-entropy regularizer, which is also referred to as the exponential weight method. Our approach includes an entropy-adaptive update rule for learning rates, originally developed for online learning in feedback graph contexts ito2022nearly. This strategy has been proven effective in providing BoBW guarantees for exponential-weight-based algorithms across various sequential decision-making problems, such as multi-armed bandits jin2023improved, partial monitoring tsuchiya2023best, linear bandits kong2023best, episodic Markov Decision Processes (MDPs) dann2023best, and sparse multi-armed bandits tsuchiya2023stability. However, a common limitation of these results, stemming from the negative-entropy regularization, is the additional $\log T$ factors in the regret bounds. A promising future direction to mitigate this could be exploring alternative regularizers like Tsallis entropy or logarithmic barriers.

Problem Setting

Suppose that there are $T$ rounds and $K$ arms. In each round $t\in[T] := \{1,2,\dots,T\}$, a decision-maker observes a context $X_t\in\mathcal{X}\subset \mathbb{R}^d$, where $\mathcal{X}$ is a context space. Then, the decision-maker chooses an arm $A_t\in[K] := \{1,2,\dots, K\}$ based on the context $X_t$ and past observations. Each arm $a\in[K]$ is linked to a loss $\ell_{t}(a, X_t)$, which depends on $X_t$ and round $t$. After choosing arm $A_t$ in round $t$, the decision-maker incurs the loss $\ell_{t}(A_t, X_t)$. Our goal is to minimize the cumulative loss $\sum^T_{t=1}\ell_{t}(A_t, X_t)$. We introduce the setting in more detail in the following part.

\paragraph{Contextual distribution.} Let a distribution of $X_t$ be $\mathcal{D}$, which is invariant across $t\in[T]$. We also assume that $\mathcal{D}$ is known to the decision-maker.

assumption[Contextual distribution] The context $X_t$ is an i.i.d. random variable, whose distribution $\mathcal{D}$ is known to the decision-maker, and the covariance matrix $\Sigma = \mathbb{E}\left[X_t X^\top_t\right]$ is positive definite with its smallest eigenvalue $\lambda_{\min} > 0$.

\paragraph{Loss.} In each round $t\in[T]$, a context is sampled from $\mathcal{D}$ and the environment chooses $\ell_t(\cdot, X_t)$ based on the past observations $\mathcal{F}_{t-1} = (X_1, A_1, \ell_1(A_1, X_1), X_2, \dots, X_{t-1}, A_{t-1}, \ell_{t-1}(A_{t-1}, X_{t-1}))$. We consider a general framework where $\ell_t$ is generated in both stochastic and adversarial ways. See Section (ref) for details.

\paragraph{Policy.} We refer to a function that determines the arm draw as a policy. Let $\Pi$ be a set of all possible policies $\pi:\mathcal{X}\to \mathcal{P} := \Big\{ u = (u_1\ u_2\ \dots\ u_K)^\top \in [0, 1]^K \mid \sum^K_{k=1}u_k = 1 \Big\}$. Let $\pi(a\mid x)$ be the $a$-th element of $\pi(x)$. The goal of the decision-maker is to minimize the cumulative loss $\sum^T_{t=1}\ell_t(A_t, X_t)$ incurred through $T$ rounds by learning a policy $\pi\in\Pi$.

\paragraph{Procedure in a trial.} In each round of a trial, the decision-maker first observes a context and then chooses an action based on the context and past observations obtained until the round. Specifically, we consider sequential decision-making with the following steps in each round $t\in[T]$:

enumerate• The environment decides $\big(\ell_t(1, X_t), \ell_t(2, X_t), \dots, \ell_t(K, X_t)\big)$ based on $\mathcal{F}_{t-1}$. • The decision-maker observes the context $X_t$, which is generated from a known distribution $\mathcal{D}$. • Based on the context $X_t$, the decision-maker chooses a policy $\pi_t(X_t) \in \mathcal{P}$. • The decision-maker chooses action $A_t \in [K]$ with probability $\pi_t(a\mid X_t)$. • The decision-maker incurs the loss $\ell_t(A_t, X_t)$.

The goal of the decision-maker is to choose actions in a way that the total loss is as small as possible.

Linear Contextual Bandits

This study assumes linear models between $\ell_t(A_t, X_t)$ and $X_t$ as follows.

assumption[Linear models] For each $\ell_t(a, X_t)$, the following holds: \begin{align*} \ell_t(a, X_t) = x^\top_t \theta_{t}(a) + \varepsilon_{t}(a), \end{align*} where $\theta_{t}(a)$ is a $d$-dimensional parameter, and $\varepsilon_{t}(a)$ is the error term independent of the sequence $\{X_t\}_{t\in[T]}$.

For linear models and variables, we make the following assumptions.

assumption[Bounded variables] We assume the following: \begin{enumerate} • There exists an universal constant $C_{\mathcal{X}} > 0$ such that for each $x \in\mathcal{X}$, $\|x\|_2 \leq C_{\mathcal{X}}$ holds. • There exists an universal constant $C_{\Theta} > 0$ such that for each $\theta \in\Theta$, $\|\theta\|_2 \leq C_{\Theta}$ holds. • There exists an universal constant $C_{\mathcal{E}} > 0$ such that $|\varepsilon_{t}(a)| \leq C_{\mathcal{E}}$ holds. \end{enumerate}

Under this assumption, there exists $C_{\ell} := C(C_{\mathcal{X}}, C_{\Theta}, C_{\mathcal{E}})$ such that for all $\ell_t(a, X_t)$, the following holds for each $a\in[K]$ and $x\in\mathcal{X}$:

align*[align* omitted — 43 chars of source]

Regret

This section provides the definition of the regret, a relative measure of the cumulative loss. We evaluate the performance of the decision or policy of the decision-maker by using regret. Let $\mathcal{R}$ be a set of all possible $\rho:\mathcal{X}\to [K]$. The quality of a decision by the decision-maker is measured by its total expected regret, defined as

align*[align* omitted — 269 chars of source]

where the expectation is taken over the randomness of policies of the decision-maker, as well as the sequence of random contexts, $\{X_t\}_{t\in[T]}$, and losses, $\{\ell_t(\cdot, X_t)\}_{t\in[T]}$.

Let $X_0$ be an i.i.d. random variable from the distribution of $X_t$. Then, because $X_t$ is an i.i.d. random variable from $\mathcal{D}$, we have

align*[align* omitted — 310 chars of source]

Based on this inequality, we define an optimal policy $a^*$ as

align*[align* omitted — 140 chars of source]

Then, we have

align*[align* omitted — 131 chars of source]

Neu2020 refers to $\rho$ as linear-classifier policies, while $\pi_t$ is called stochastic policies. In our study, decision-makers compare their stochastic policies $\pi_t$ to the optimal linear-classifier policy $a^*$ using the regret.

Linear Contextual Adversarial Regime with a Self-Bounding Constraint

Then, we define the framework of a linear contextual adversarial regime with a self-bounding constraint, which is a generalization of adversarial and stochastic bandits.

definition[Linear contextual adversarial regime with a self-bounding constraint] We say that an environment is in an adversarial regime with a $(\Delta_*, C, T)$ self-bounding constraint for some $\Delta_*, C > 0$ if $R_T$ is lower bounded as \begin{align*} R_T \geq \Delta_* \cdot \mathbb{E}\left[\sum^T_{t=1}\Big( 1 - \pi_t(a^*_T(X_0)\mid X_0) \Big)\right] - C. \end{align*}

The contextual adversarial regime with a self-bounding constraint includes several important settings. Among them, we raise linear contextual bandits in stochastic bandits and adversarial bandits below.

example[Linear contextual bandits in stochastic bandits.] In stochastic bandits, the bandit models are fixed; that is, $\big(X_t, \ell_t(1, X_t), \dots, \ell_t(K, X_t)\big)$ are generated from a fixed distribution $P_0$. Let $\theta_{1}(a) = \cdots \theta_{T}(a) = \theta_0(a)$. Note that when considering stochastic bandits, we have $\mathbb{E}\left[\theta_{t}(a)\right] = \theta_0(a)$ and \begin{align*} a^*_T(x) = \operatorname*{arg\,min}_{a\in[K]} \sum^T_{t=1}\Big\langle x, \mathbb{E}\left[\theta_{t}(a)\right]\Big\rangle = \operatorname*{arg\,min}_{a\in[K]} \Big\langle x, \theta_{0}(a)\Big\rangle\qquad \forall x \in \mathcal{X}. \end{align*} Let $a^*_T(x)$ be $a^*_0(x)$. In this setting, we assume that for each $P_0$, there exist positive constraints $\Delta_*$ such that for all $x \in \mathcal{X}$, \begin{align} \min_{b\neq a^*_0(x)}\Big\langle x, \theta_0(b)\Big\rangle - \Big\langle x, \theta_{0}(a^*_0(x))\Big\rangle \geq \Delta_*. \end{align} Then, the regret can be lower bounded as $R_T \geq \Delta_* \cdot \mathbb{E}\left[\sum^T_{t=1}\Big( 1 - \pi_t(a^*_0(X_0)\mid X_0) \Big)\right]$ (See Appendix (ref)).

example[Linear contextual bandits in adversarial bandits] In adversarial bandits, we do not assume any data-generating process for the $\ell_t(a, X_t)$, and the loss is decided to increase the regret based on the past observations $\mathcal{F}_{t-1}$.

remark[Margin conditions] In linear contextual bandits, we often employ the margin condition to characterize the difficulty of the problem instance. The margin condition is defined as follows Li2021regret: there exist $\Delta_*$, $C_1$, $a^*$, and $\alpha \in [0, +\infty]$, such that for $h\in\left[C_1\sqrt{\frac{\log(d)}{T}}, \Delta_*\right]$, \[\mathbb{P}\left(\Big\langle X_t, \theta_{t}(a^*)\Big\rangle \leq \max_{b \neq a^*}\Big\langle X_t, \theta_{t}(b)\Big\rangle + h\right)\leq \frac{1}{2}\left(\frac{h}{\Delta_*}\right)^\alpha.\] Our definition of the linear contextual adversarial regime with a self-bounding constraint corresponds to a case with $\alpha = \infty$. Extending our results to more general $\alpha$ is a future work.

remark[Linear contextual bandits with corruption in existing studies] Lykouris2018, Gupta2019, zhao2021linear, and he2022nearly propose another definition of linear contextual contextual bandits with corruption. In their work, instead of our defined $\ell_t(a, X_t)$, they define a loss as \begin{align*} \widetilde{\ell}_t(a, X_t) = \ell_t(a, X_t) + \widetilde{c}_t(a), \end{align*} where $\widetilde{c}_t(a)$ is an adversarial corruption term. For simplicity, let $\widetilde{c}_t(a) \in [-1, 1]$. In zhao2021linear, the degree of the corruption is determined by $\widetilde{C} \in [0, T]$ defined as $\widetilde{C} = \sum^T_{t=1}\max_{a\in[K]}|c_t(a)|$. In Lykouris2018, Gupta2019, and he2022nearly, the corruption level is determined by another parameter $\widetilde{C}^\dagger \in [0, T]$ defined as $\sum^T_{t = 1}|c_t(A_t)|$. Here, $\widetilde{C} \geq \widetilde{C}^\dagger$ holds. Note that the adversarial corruption depends on $A_t$ in he2022nearly, while the adversarial corruption is determined irrelevant to $A_t$ in Lykouris2018, Gupta2019, and he2022nearly. Unlike ours, they do not assume the existence of $\Delta_*$ defined in (ref). In this sense, our results and their results are complementary.

Algorithm

This section provides an algorithm for our defined problem. Our proposed algorithm is a generalization of the {\tt RealLinEXP3} algorithm proposed by Neu2020. We extend the method by employing the Follow-The-Regularized-Leader (FTRL) approach with round-varying arm-drawing probabilities. Our design of the algorithm is also motivated by existing studies about Best-of-Both-Worlds (BoBW) algorithms in different Multi-Armed Bandit (MAB) problems, such as ito2022nearly.

In our setting, we first observe a context and then draw an arm based on that context. We consider stochastically drawing an arm. Therefore, in designing the algorithm, our interest lies in appropriately defining the arm-drawing probability. In the FTRL approach, we define this probability by utilizing an unbiased estimator of the loss function.

We refer to our proposed algorithm as {\tt BoBW-RealFTRL} because it modifies the {\tt RealLinEXP3} for a best-of-both-worlds algorithm using the FTRL framework. The pseudo-code is shown in Algorithm (ref). In the following part, we explain the algorithm.

\paragraph{Unbiased loss estimator.} For each $a\in[K]$, let us define an estimator of regression parameters as

align*[align* omitted — 106 chars of source]

where $\Sigma^{\dagger}_{t, a}$ is an estimator of $\mathbb{E}\left[\mathbbm{1}[A_t = a]X^\top_0 X_0\right]^{-1}$. Then, the loss can be estimated as

align*[align* omitted — 99 chars of source]

In analysis of adversarial bandits, the bias of $\widehat{\ell}_{t}(a, x)$ plays an important role. If $\Sigma^{\dagger}_{t, a} = \mathbb{E}\left[\mathbbm{1}[A_t = a]X^\top_0 X_0\mid \mathcal{F}_{t-1}\right]^{-1}$, then this loss estimator is unbiased for $x^\top\theta_0(a)$ because

align*[align* omitted — 452 chars of source]

Note that in our algorithm, $\Sigma^{\dagger}_{t, a}$ is just an estimator of $\mathbb{E}\left[\mathbbm{1}[A_t = a]X^\top_0 X_0\mid \mathcal{F}_{t-1}\right]^{-1}$, and $\Sigma^{\dagger}_{t, a} = \mathbb{E}\left[\mathbbm{1}[A_t = a]X^\top_0 X_0\mid \mathcal{F}_{t-1}\right]^{-1}$ does not hold in general. Therefore, $\widehat{\ell}_{t}(a, x)$ is not unbiased. However, we can show that the bias can be ignored because it is sufficiently small to evaluate the regret in depth. We also define a vector of loss estimators as $\widehat{\ell}_{t}(x) = \left(\widehat{\ell}_{t}(1, x)\ \ \widehat{\ell}_{t}(2, x)\ \ \cdots\ \ \widehat{\ell}_{t}(K, x)\right)^\top$.

\paragraph{Estimation of $\mathbb{E}\left[\mathbbm{1}[A_t = a]X^\top_0 X_0\mid \mathcal{F}_{t-1}\right]^{-1}$.} Our remaining task is to estimate $\mathbb{E}\left[\mathbbm{1}[A_t = a]X^\top_0 X_0\mid \mathcal{F}_{t-1}\right]^{-1}$. The difficulty of this task stems from the dependency on $A_t$, which varies across rounds. To address this issue, we consider Matrix Geometric Resampling (MGR) proposed by Neu2020.

The MGR assumes that we have access to the distribution $\mathcal{D}$ of $X_t$ and estimates $\mathbb{E}\left[\mathbbm{1}[A_t = a]X^\top_0 X_0\right]^{-1}$ by using simulations. We introduce the algorithm in Algorithm (ref).

In Algorithm (ref), we define $W_{k, a}$ for which $\mathbb{E}[W_{k, a} \mid \mathcal{F}_{t-1}] = \Sigma_{t, a}$ holds. Here, from the independence of the context $X(k)$ from each other, we also have $\mathbb{E}[V_{k, a} \mid \mathcal{F}_{t-1}] = \mathbb{E}\left[ \prod^k_{j=1} \big( I - \delta W_{j, a}\big) \mid \mathcal{F}_{t-1}\right] = (I - \delta \Sigma_{t, a})^k$. Therefore, $\widehat{\Sigma}^\dagger_{t, a}$ works as a good estimator of $\Sigma^{-1}_{t, a}$ on expectations when $M_t = \infty$ because

align*[align* omitted — 280 chars of source]

holds.

In implementation, $M_t$ is finite, and we introduce an approximation error of $\Sigma^{-1}_{t, a}$ with finite $M_t$ in Lemma (ref).

\paragraph{Our proposed algorithm: {\tt BoBW-RealFTRL}.} Then, we define our policy, called the {\tt BoBW-RealFTRL}, as

align[align omitted — 96 chars of source]

where $\iota$ is a $K$-dimensional vector $\iota = (1\ 1\ \cdots\ 1)^\top$,

align[align omitted — 819 chars of source]

This algorithm is an extension of the {\tt RealLinEXP3} proposed by Neu2020 and the FTRL. In the studies of BoBW algorithms, the FTRL-based algorithms are often employed, and our algorithm is connected to the literature.

algorithm[algorithm omitted — 637 chars of source]

algorithm[algorithm omitted — 605 chars of source]

Regret Analysis

This section provides upper bounds for the regret of our proposed {\tt BoBW-RealFTRL} algorithm.

For notational simplicity, let us denote $a^*_T$ by $a^*$. To derive upper bounds, we define the following quantities:

align*[align* omitted — 158 chars of source]

Then, we show the following upper bound, which holds for general cases such as adversarial and stochastic environments. We show the proof in Sections (ref) and (ref).

theorem[General regret bounds] If the environment generates losses under the contextual adversarial regime with a self-bounding constraint (Definition (ref)), the {\tt BoBW-RealFTRL} with $\widehat{\Sigma}^\dagger_{t, a}$ incurs the total regret \begin{align*} R_T \leq O\left(\left( \frac{K\log(T)}{\beta_1}\left(\frac{\log(T)}{ \delta \lambda_{\min}\log(K)} + d\right) + \beta_1\sqrt{\log(K)}\right)\sqrt{\log(KT)}\max\Big\{\overline{Q}^{1/2}(a^*), 1\Big\}\right). \end{align*}

For each situation, such as adversarial environments and linear contextual adversarial regimes with a self-bounding constraint, we derive a specific upper bound.

First, from $\overline{Q}(a^*) \leq T$, the following regret bound holds without any assumptions on the loss; that is, it holds for an adversarial environment.

corollaryAssume the same conditions in Theorem (ref). Then, under an adversarial environment, the regret satisfies \[R_T = O\left(\left( \frac{K\log(T)}{\beta_1}\left(\frac{\log(T)}{ \delta \lambda_{\min}\log(K)} + d\right) + \beta_1\sqrt{\log(K)}\right)\sqrt{\log(KT)}\sqrt{T}\right);\] that is, from $\beta_1 = \omega \sqrt{ {K\log(T)}\left(\frac{\log(T)}{ \delta \lambda_{\min}\log(K)} + d\right)}$, \[R_T = {O}\left(\log(KT)\sqrt{ {K\log(K)T\log(T)}\left(\frac{\log(T)}{ \delta \lambda_{\min}\log(K)} + d\right)}\right)\] holds.

Furthermore, we derive a regret bound under the linear contextual adversarial regime with a self-bounding constraint.

corollary[Regret bounds under the linear contextual adversarial regime with a self-bounding constraint] Suppose that the same conditions in Theorem (ref) hold. Then, under the contextual adversarial regime with self-bounding constraints, the regret satisfies \begin{align*} R_T &= O\Bigg(\left\{ \frac{K\log(T)}{\beta_1}\left(\frac{\log(T)}{ \delta \lambda_{\min}\log(K)} + d\right) + \beta_1\sqrt{\log(K)}\right\}^2\log(KT)/ \Delta_{*}\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + \sqrt{{C\left\{\frac{K\log(T)}{\beta_1}\left(\frac{\log(T)}{ \delta \lambda_{\min}\log(K)} + d\right) + \beta_1\sqrt{\log(K)}\right\}^2}\log(KT)/{\Delta_{*}}}\Bigg); \end{align*} that is, from $\beta_1 = \omega \sqrt{ {K\log(T)}\left(\frac{\log(T)}{ \delta \lambda_{\min}\log(K)} + d\right)}$, \[R_T = O\left(\frac{D}{\Delta_{*}} + \sqrt{\frac{CD}{\Delta_{*}}}\right)\] holds, where \begin{align*} D = {K\log(K)\log(T)}\left(\frac{\log(T)}{ \delta \lambda_{\min}\log(K)} + d\right)\log(KT). \end{align*}

The result in Corollary (ref) implies $R_T = O\left(\frac{(\log(T))^3}{\Delta_{*}} + \sqrt{\frac{C(\log(T))^3}{\Delta_{*}}}\right)$.

proofFrom the definition of the contextual adversarial regime with a self-bounding constraint, we have \begin{align*} R_T \geq \Delta_* \cdot \mathbb{E}\left[\sum^T_{t=1}\Big( 1 - \pi_t(a^*(X_0)\mid X_0) \Big)\right] - C = \Delta_* \cdot \overline{Q}(a^*) - C. \end{align*} Therefore, from Lemma (ref), for any $\lambda > 0$, we have \begin{align*} &R_T = (1+\lambda)R_T - \lambda R_T\\ &= (1+\lambda)O\left(c\sqrt{\log(KT)}\sqrt{\sum^T_{t=1}\mathbb{E}\left[H(q_t(X_0))\right]}\right) - \lambda R_T\\ &\leq (1+\lambda)O\left(c\sqrt{\log(KT)}\sqrt{\sum^T_{t=1}\mathbb{E}\left[H(q_t(X_0))\right]}\right) - \lambda \Delta_* \cdot \overline{Q}(a^*) + \lambda C, \end{align*} where \[c = \left( \frac{K\log(T)}{\beta_1}\left(\frac{\log(T)}{ \delta \lambda_{\min}\log(K)} + d\right) + \beta_1\sqrt{\log(K)}\right).\] Here, as well as the proof of Theorem (ref), from Lemma (ref), if $Q(a^*\mid x) \leq e$, we have $\sum^T_{t=1}H(q_t(x)) \leq e\log(KT)$ and otherwise, we have $\sum^T_{t=1}H(q_t(x)) \leq Q(a^*\mid x)\log(KT)$. Hence, we have $\sum^T_{t=1}H(q_t(x)) \leq \log(KT)\max\{e, Q(a^*\mid x)\}$. Here, to upper bound $R_T$, it is enough to only consider a case with $Q(a^*\mid x) \geq e$, and we obtain \begin{align*} &R_T \leq (1+\lambda)O\left(c\sqrt{\log(KT)}\sqrt{\overline{Q}(a^*)\log(KT)}\right) - \lambda \Delta_* \cdot \overline{Q}(a^*) + \lambda C\leq \frac{O\left(\Big\{(1+\lambda)c\Big\}^2\sqrt{\log(KT)}\right)}{2\lambda\Delta_*} + \lambda \Delta_*. \end{align*} where the second inequality follows from $a\sqrt{b} - \frac{c}{2}b \leq \frac{a^2}{c^2}$ holds for any $a,b,c > 0$. By choosing \[\lambda = \sqrt{\frac{c^2\log(KT)}{\Delta_*}\Big/ \left(\frac{c^2\log(KT)}{\Delta_*} + 2C\right)}.\] Then, we obtain $R_T = O\Bigg(c^2\log(KT)/ \Delta_{*} + \sqrt{{Cc^2}\log(KT)/{\Delta_{*}}}\Bigg)$.

In the following sections, we show the proof procedure of Theorem (ref).

Preliminaries for the Proof of Theorem (ref)

Let $X_0$ be a sample from the context distribution $\mathcal{D}$ independent of $\mathcal{F}_T$. Let $D_t(p, q)$ denote the Bregman divergence of $p. q\in\Pi$ with respect to $\psi_t$; that is,

align*[align* omitted — 102 chars of source]

Let us define $\pi^*\in \Pi$ as $\pi^*(a^*(x)\mid x) = 1$ and $\pi^*(a\mid x) = 0$ for all $a\in[K]\backslash \{a^*(x)\}$.

Then, the following lemma holds. The proof is shown in Appendix (ref)

lemmaIf $A_t$ is chosen as our proposed method, the regret is bounded by \begin{align*} R_T &\leq \mathbb{E}\Bigg[\sum^T_{t=1}\Big\{\gamma_t + \left\langle \widehat{\ell}_t(X_0), q_t(X_0) - q_{t+1}(X_0) \right\rangle\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ - D_t(q_{t+1}(X_0), q_t(X_0)) + \psi_t(q_{t+1}(X_0)) - \psi_{t+1}(q_{t+1}(X_0))\Big\}\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + \psi_{T+1}(\pi^*(X_0)) - \psi_1(q_1(X_0))\Bigg] + 2\sum^T_{t=1}\max_{a\in[K]}\left| \mathbb{E}\left[\langle X_t, \theta_{t}(a) - \widehat{\theta}_{t}(a) \rangle\right] \right|. \end{align*}

To show Lemma (ref), we use the following proposition from Neu2020.

propositionSuppose that $\pi_t\in\mathcal{F}_{t-1}$ and that $\mathbb{E}\left[\widehat{\theta}_{t, a}|\mathcal{F}_{t-1}\right] = \theta_{t, a}$ for all $t, a$ hold. Then, the following holds: \begin{align*} \mathbb{E}\left[\sum^T_{t=1}\sum_{a\in[K]}\Big(\pi_t(a\mid X_t) - \pi^*(a\mid X_t)\Big)\Big\langle X_t, \theta_{t,a}\Big\rangle\right] = \mathbb{E}\left[\sum^T_{t=1}\sum_{a\in[K]}\Big(\pi_t(a\mid X_0) - \pi^*(a\mid X_0)\Big)\Big\langle X, \widehat{\theta}_{t,a}\Big\rangle\right]. \end{align*}

This proposition plays an important role throughout this study.

\paragraph{Bounding the stability term.} For the stability term $\left\langle \widehat{\ell}_t(X_0), q_t(X_0) - q_{t+1}(X_0) \right\rangle - D_t(q_{t+1}(X_0), q_t(X_0))$, we use the following proposition from ito2022nearly.

proposition[From Lemma 8 in ito2022nearly] If $\psi_t$ is given as (ref), for any $\ell: \mathcal{X} \to \mathbb{R}^K$ and $p, q \in\Pi$, we have \begin{align*} &\Big\langle \ell(x), p(x) - q(x) \Big\rangle - D_t(q(x), p(x)) \leq \beta_t\sum_{a\in[K]}p(a\mid x)\xi\left(\frac{\ell(a, x)}{\beta_t}\right). \end{align*} for any $x\in\mathcal{X}$, where $\xi(x) := \exp(-x) + x - 1$.

For $\widehat{\ell}(a, x)$, if $\frac{\widehat{\ell}(a, x)}{\beta_t} \geq -1$ holds, then Proposition (ref) implies

align*[align* omitted — 184 chars of source]

For the RHS, we apply the following proposition from Neu2020.

proposition[From Lemma 6 in Neu2020] For each $t\in[T]$, our strategy satisfies \begin{align*} \mathbb{E}\left[\sum_{a\in[K]}\pi_t(a\mid X_0)\widehat{\ell}^2_t(a, X_0)\mid \mathcal{F}_{t-1}\right] \leq 3Kd. \end{align*}

\paragraph{Estimation error of the design matrix.} Next, we bound $\sum^T_{t=1}\max_{a\in[K]}\left| \mathbb{E}\left[\langle X_t, \theta_{t}(a) - \widehat{\theta}_{t}(a) \rangle\right] \right|$. An upper bound of $\sum^T_{t=1}\max_{a\in[K]}\left| \mathbb{E}\left[\langle X_t, \theta_{t}(a) - \widehat{\theta}_{t}(a) \rangle\right] \right|$ is given as the following lemma.

lemmaWe have $\left| \mathbb{E}\left[\langle X_t, \theta_{t}(a) - \widehat{\theta}_{t}(a) \rangle\right] \right| \leq C_{\mathcal{X}} C_{\Theta} / T$.

proof[Proof of Lemma (ref)] From Lemma 5 in Neu2020, we have $\left| \mathbb{E}\left[\langle X_t, \theta_{t}(a) - \widehat{\theta}_{t}(a) \rangle\right] \right| \leq C_{\mathcal{X}} C_{\Theta} \exp\left( - \frac{\gamma_t \delta}{K}\lambda_{\min}M_t\right)$. Then, we have \begin{align*} &\exp\left( - \frac{\gamma_t \delta}{K}\lambda_{\min}M_t\right) = \exp\left(-\frac{K\log(T)}{\delta \lambda_{\min}\cdot 2\beta_t}\frac{\delta\lambda_{\min}}{K}M_t\right)\\ &\leq \exp\left(-\frac{K\log(T)}{\delta \lambda_{\min}\cdot \left(2\beta_t - 1\right)}\frac{\delta\lambda_{\min}}{K}M_t\right)= \exp\left(-\log(T)\right) = \frac{1}{T}, \end{align*} where recall that we defined $M_t = \beta_t - 1 $

Proof of Theorem (ref)

Then, we show the following lemma. The proof is shown in Appendix (ref).

lemmaThe regret for the {\tt BoBW-RealFTRL} with $\widehat{\Sigma}^\dagger_{t, a}$ is bounded as \begin{align*} R_T &\leq \mathbb{E}\left[\sum^T_{t=1}\Bigg\{\gamma_t + \frac{3Kd}{\beta_t} + \left(\beta_{t+1} - \beta_t\right)H(q_{t+1}(X_0))\Bigg\}\right] + \beta_1\log(K) + 2 C_{\mathcal{X}} C_{\Theta}. \end{align*}

From this result, we obtain the following lemma. We provide the proof in Appendix (ref)

lemmaAssume the conditions in Theorem (ref). Suppose that $\beta_t$ and $\gamma_t$ satisfy (ref) and (ref). Then, we have \begin{align*} R_T \leq \overline{c} \sqrt{\mathbb{E}\left[\sum^T_{t=1}H(q_t(X_0))\right]} + 2 C_{\mathcal{X}} C_{\Theta}, \end{align*} where $\overline{c} = O\left( \frac{K\log(T)}{\beta_1}\left(\frac{\log(T)}{ \delta \lambda_{\min}\log(K)} + d\right) + \beta_1\sqrt{\log(K)}\right)$.

Next, we consider bounding $\sum^T_{t=1}H(q_t(x))$ by $Q(a^*\mid x)$ as shown in the following lemma.

lemmaFor any $a^*:\mathcal{X}\to[K]$, the following holds: \begin{align*} \sum^T_{t=1}H(q_t(x)) \leq Q(a^*\mid x) \log\left(\frac{eKT}{Q(a^*\mid x)}\right), \end{align*} where $e$ is Napier's constant.

By using the above lemmas and propositions, we prove Theorem (ref).

proof[Proof of Theorem (ref)] From Lemma (ref), if $Q(a^*\mid x) \leq e$, we have $\sum^T_{t=1}H(q_t(x)) \leq e\log(KT)$ and otherwise, we have $\sum^T_{t=1}H(q_t(x)) \leq Q(a^*\mid x)\log(KT)$. Hence, we have $\sum^T_{t=1}H(q_t(x)) \leq \log(KT)\max\{e, Q(a^*\mid x)\}$. From Lemma (ref), we have \begin{align*} R_T &\leq \overline{c} \sqrt{\sum^T_{t=1}\mathbb{E}\left[H(q_t(X_0))\right]} + 2 C_{\mathcal{X}} C_{\Theta}\\ &\leq O\left(\left( \frac{K\log(T)}{\beta_1}\left(\frac{\log(T)}{ \delta \lambda_{\min}\log(K)} + d\right) + \beta_1\sqrt{\log(K)} \right)\sqrt{\log(KT)}\max\Big\{\overline{Q}^{1/2}, 1\Big\}\right). \end{align*}

Conclusion

We developed a BoBW algorithm for linear contextual bandits. Our proposed algorithm is based on the FTRL approach. In our theoretical analysis, we show that the upper bounds of the proposed algorithm are given as $O\left(\min\left\{\frac{D}{\Delta_{*}} + \sqrt{\frac{CD}{\Delta_{*}}}, \sqrt{\log(KT)TD}\right\}\right)$, where $D = {K\log(T)}\left(\log(T) + d\log(K)\right)\log(KT)$. This regret upper bound implies $O\left(\min\left\{\sqrt{\frac{TD}{\Delta_{*}}}, \sqrt{\log(KT)TD}\right\}\right)$ regret in an adversarial environment and $O\left(\frac{D}{\Delta_{*}}\right)$ regret in an adversarial environment and $O\left(\frac{D}{\Delta_{*}}\right)$ regret in a stochastic environment. This result also implies $O\left(\frac{(\log(T))^3}{\Delta_{*}}\right)$ regret in a stochastic regime and $O\left(\sqrt{T}(\log(T))^2\right)$ regret in an adversarial regime with respect to $T$.

There are four directions for future work in this study. The first direction is to develop an algorithm that does not require a contextual distribution while maintaining the BoBW property. We expect this extension can be accomplished by applying our proposed method to a method proposed by liu2023bypassing, based on the FTRL approach with the log-determinant barrier. We note that standard linear contextual bandits in a stochastic environment do not require the contextual distribution to be known, but it is required for dealing with an adversarial environment.

The second direction is to provide lower bounds in our adversarial regimes. In existing studies, Li2021regret provides a general upper bound that holds for a high-dimensional setting with various margin conditions. We can incorporate such results to derive a lower bound in our problem setting.

The third extension is to develop an algorithm that works for linear contextual bandits without assuming a specific minimum gap constant $\Delta_{*}$. To address this issue, we might use the margin condition to generalize the minimum gap assumption. Lastly, tightening our regret upper bound is also an open problem.