An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits

Introduction

We study the contextual linear bandit (CLB) setting [e.g., 1], where at each time step $t$ the learner observes a context $X_{t}$ drawn from a context distribution $\rho$, pulls an arm $A_{t}$, and receives a reward $Y_{t}$ drawn from a distribution whose expected value is a linear combination between $d$-dimensional features $\phi(X_{t},A_{t})$ describing context and arm, and an unknown parameter $\theta^{\star}$. The objective of the learner is to maximize the reward over time, that is to minimize the cumulative regret w.r.t. an optimal strategy that selects the best arm in each context. This setting formalizes a wide range of problems such as online recommendation systems, clinical trials, dialogue systems, and many others . Popular algorithmic principles, such as optimism-in-face-of-uncertainty and Thompson sampling , have been applied to this setting leading to algorithms such as OFUL and LinTS with strong finite-time worst-case regret guarantees. Nonetheless, Lattimore & Szepesvari recently showed that these algorithms are not asymptotically optimal (in a problem-dependent sense) as they fail to adapt to the structure of the problem at hand. In fact, in the CLB setting, the values of different arms are tightly connected through the linear assumption and a possibly suboptimal arm may provide a large amount of information about $\theta^{\star}$ and thus the optimal arm. Optimistic algorithms naturally discard suboptimal arms and thus may miss the chance to acquire information about $\theta^{\star}$ and significantly reduce the regret.

Early attempts to exploit general structures in MAB either adapted UCB-based strategies or focused on different criteria, such as regret to information ratio . While these approaches succeed in improving the finite-time performance of optimism-based algorithms, they still do not achieve asymptotic optimality. An alternative approach to exploit the problem structure was introduced in for (non-contextual) linear bandits. Inspired by approaches for regret minimization and best-arm identification in MAB, Lattimore & Szepesvari proposed to compute an exploration strategy by solving the (estimated) optimization problem characterizing the asymptotic regret lower bound for linear bandits. While the resulting algorithm matches the asymptotic logarithmic lower bound with tight leading constant, it performs rather poorly in practice. Combes et al. followed a similar approach and proposed OSSB, an asymptotically optimal algorithm for bandit problems with general structure (including, e.g., linear, Lipschitz, unimodal). Unfortunately, once instantiated for the linear bandit case, OSSB suffers from poor empirical performance due to the large dependency on the number of arms. Recently, Hao et al. introduced OAM, an asymptotically optimal algorithm for the CLB setting. While OAM effectively exploits the linear structure and outperforms other bandit algorithms, it suffers from major limitations. From an algorithmic perspective, at each exploration step, OAM requires solving the optimization problem of the regret lower bound, which can hardly scale beyond problems with a handful of contexts and arms. Furthermore, OAM implements a forcing exploration strategy that often leads to long periods of linear regret and introduces a linear dependence on the number of arms $|\mathcal{A}|$. Finally, the regret analysis reveals a critical dependence on the inverse of the smallest probability of a context (i.e., $\min_{x}\rho(x)$), thus suggesting that OAM may suffer from poor finite-time performance in problems with unbalanced context distributions.Interestingly, Hao et al. explicitly mention in their conclusions the importance of properly managing the context distribution to achieve satisfactory finite-time performance. Degenne et al. recently introduced SPL, which significantly improves over previous algorithms for MAB problems with general structures. Inspired by algorithms for best-arm identification , Degenne et al. reformulate the optimization problem in the lower bound as a saddle-point problem and show how to leverage online learning methods to avoid recomputing the exploration strategy from scratch at each step. Furthermore, SPL removes any form of forced exploration by introducing optimism into the estimated optimization problem. As a result, SPL is computationally efficient and achieves better empirical performance in problems with general structures.

Contributions. In this paper, we follow similar steps as in and introduce SOLID, a novel algorithm for the CLB setting. Our main contributions can be summarized as follows.

We first reformulate the optimization problem associated with the lower bound for contextual linear bandits by introducing an additional constraint to guarantee bounded solutions and by explicitly decoupling the context distribution and the exploration policy. While we bound the bias introduced by the constraint, we also illustrate how the resulting exploration policy is better adapted to unbalanced context distributions.

Leveraging the Lagrangian dual formulation associated with the constrained lower-bound optimization problem, we derive SOLID, an efficient primal-dual learning algorithm that incrementally updates the exploration strategy at each time step. Furthermore, we replace forced exploration with an optimistic version of the optimization problem by specifically leveraging the linear structure of the problem. Finally, SOLID does not require any explicit tracking step and it samples directly from the current exploration strategy.

We establish the asymptotic optimality of SOLID, while deriving a finite-time problem-dependent regret bound that scales only with $\log|\mathcal{A}|$ and without any dependence on $\min_{x}\rho(x)$. To this purpose, we introduce a new concentration bound for regularized least-squares that scales as $\mathcal{O}(\log t+d\log\log t)$, hence removing the $d\log t$ dependence of the bound in . Moreover, we establish a $\widetilde{\mathcal{O}}((\sqrt{d}+|\mathcal{X}|)\sqrt{dn})$ worst-case regret bound for any CLB problem with $|\mathcal{X}|$ contexts, $d$ features, and horizon $n$. Notably, this is implies that SOLID is the first algorithm to be simultaneously asymptotically optimal and minimax optimal when $|\mathcal{X}|\leq\sqrt{d}$ (e.g., in non-contextual linear bandits, when $|\mathcal{X}|=1$).

We empirically compare to a number of state-of-the-art methods for contextual linear bandits and show how SOLID is more computationally efficient and often has the smallest regret.

A thorough comparison between SOLID and related work is reported in App. B.

Preliminaries

Regularized least-squares estimator. We introduce the regularized least-square estimate of $\theta^{\star}$ using $t$ samples as $\widehat{\theta}_{t}:=\overline{V}_{t}^{-1}U_{t}$, where $\overline{V}_{t}:=\sum_{s=1}^{t}\phi(X_{s},A_{s})\phi(X_{s},A_{s})^{\mathsf{T}}+\nu I$, with $\nu\geq\max\{L^{2},1\}$ and $I$ the $d\times d$ identity matrix, and $U_{t}:=\sum_{s=1}^{t}\phi(X_{s},A_{s})Y_{s}$. The estimator $\widehat{\theta}_{t}$ satisfies the following concentration inequality (see App. J for the proof and exact formulation).

Let $\delta\in(0,1)$, $n\geq 3$, and $\widehat{\theta}_{t}$ be a regularized least-square estimator obtained using $t\in[n]$ samples collected using an arbitrary bandit strategy $\pi:=\{\pi_{t}\}_{t\geq 1}$. Then,

where $c_{n,\delta}$ is of order $\mathcal{O}(\log(1/\delta)+d\log\log n)$.

For the usual choice $\delta=1/n$, $c_{n,1/n}$ is of order $\mathcal{O}(\log n+d\log\log n)$, which illustrates how the dependency on $d$ is on a lower-order term w.r.t. $n$ (as opposed to the well-known concentration bound derived in ). This result is the counterpart of [7, Thm. 8] for the concentration on the reward parameter estimation error instead of the prediction error and we believe it is of independent interest.

Lower Bound

Let $\pi:=\{\pi_{t}\}_{t\geq 1}$ by a uniformly good bandit strategy then,

where $v^{\star}(\theta^{\star})$ is the value of the optimization problem

where $\Omega=\{\omega(x,a)\geq 0\mid\forall x\in\mathcal{X}:\sum_{a\in\mathcal{A}}\omega(x,a)=1\}$ is the probability simplex. We denote by $\omega^{\star}_{z,\theta^{\star}}$ the optimal solution of (Pz) and $u^{\star}(z,\theta^{\star})$ its associated value (if the problem is unfeasible we set $u^{\star}(z,\theta^{\star})=+\infty$). Inspecting (Pz), we notice that $z$ serves as a global constraint on the number of samples. In fact, for any $\omega\in\Omega$, the associated number of samples $\eta(x,a)$ allocated to a context-arm pair $(x,a)$ is now $z\rho(x)\omega(x,a)$. Since $\rho$ is a distribution over $\mathcal{X}$ and $\sum_{a}\omega(x,a)=1$ in each context, the total number of samples sums to $z$. As a result, (Pz) admits a minimum and it is more amenable to designing a learning algorithm based on its Lagrangian relaxation. Furthermore, we notice that $z$ can be interpreted as defining a more “finite-time” formulation of the lower bound. Finally, we remark that the total number of samples that can be assigned to a context $x$ is indeed constrained to $z\rho(x)$. This constraint crucially makes (Pz) more context aware and forces the solution $\omega$ to be more adaptive to the context distribution. In Sect. 4, we leverage these features to design an incremental algorithm whose finite-time regret does not depend on $\rho_{\min}$, thus improving over previous algorithms , as supported by the empirical results in Sect. 6. The following lemma provides a characterization of (Pz) and its relationship with (P) (see App. C for the proof and further discussion).

The first result characterizes the range of $z$ for which (Pz) is feasible. Interestingly, $\underline{z}(\theta^{\star})<+\infty$ is the inverse of the sample complexity of the best-arm identification problem and the associated solution is the one that maximizes the amount of information gathered about the reward model $\theta^{\star}$. As $z$ increases, $\omega^{\star}_{z,\theta^{\star}}$ becomes less aggressive in favoring informative context-arm pairs and more sensitive to the regret minimization objective. The second result quantifies the bias w.r.t. the optimal solution of (Pz). For $z\geq\overline{z}(\theta^{\star})$, the error decreases approximately at a rate $1/\sqrt{z}$ showing that the solution of (Pz) can be made arbitrarily close to $v^{\star}(\theta^{\star})$.

In designing our learning algorithm, we build on the Lagrangian relaxation of (Pz). For any $\omega\in\Omega$, let $f(\omega;\theta^{\star})$ denote the objective function and $g(\omega,z;\theta^{\star})$ denote the KL constraint

We introduce the Lagrangian relaxation problem

Asymptotically Optimal Linear Primal Dual Algorithm

We introduce SOLID (aSymptotic Optimal Linear prImal Dual), which combines a primal-dual approach to incrementally compute the solution of an optimistic estimate of the Lagrangian relaxation (Pλ) within a scheme that, depending on the accuracy of the estimate $\widehat{\theta}_{t}$, separates exploration steps, where arms are pulled according to the exploration policy $\omega_{t}$, and exploitation steps, where the greedy arm is selected. The values of the input parameters for which SOLID enjoys regret guarantees are reported in Sect. 5. In the following, we detail the main ingredients composing the algorithm (see Alg. 1).

Accuracy test and tracking. Similar to previous algorithms leveraging asymptotic lower bounds, we build on the generalized likelihood ratio test [e.g., 18] to verify the accuracy of the estimate $\widehat{\theta}_{t}$. At the beginning of each step $t$, SOLID first computes $\inf_{\theta^{\prime}\in\overline{\Theta}_{t-1}}\|\widetilde{\theta}_{t-1}-\theta^{\prime}\|_{\overline{V}_{t-1}}^{2}$, where $\overline{\Theta}_{t-1}=\{\theta^{\prime}\in\Theta\ |\ \exists x\in\mathcal{X},\ a^{\star}_{\widetilde{\theta}_{t-1}}(x)\neq a^{\star}_{\theta^{\prime}}(x)\}$ is the set of alternative models. This quantity measures the accuracy of the algorithm, where the infimum over alternative models defines the problem $\theta^{\prime}$ that is closest to $\widetilde{\theta}_{t-1}$ and yet different in the optimal arm of at least one context.In practice, it is more efficient to take the infimum only over problems with different optimal arm in the last observed context $X_{t}$. This is indeed what we do in our experiments and all our theoretical results follow using this alternative definition with only minor changes. This serves as a worst-case scenario for the true $\theta^{\star}$, since if $\theta^{*}=\theta^{\prime}$ then selecting arms according to $\widetilde{\theta}_{t-1}$ would lead to linear regret. If the accuracy exceeds a threshold $\beta_{t-1}$, then SOLID performs an exploitation step, where the estimated optimal arm $a^{\star}_{\widetilde{\theta}_{t-1}}(X_{t})$ is selected in the current context. On the other hand, if the test fails, the algorithm moves to an exploration step, where an arm $A_{t}$ is sampled according to the estimated exploration policy $\omega_{t}(X_{t},\cdot)$. While this approach is considerably simpler than standard tracking strategies (e.g., selecting the arm with the largest gap between the policy $\omega_{t}$ and the number of pulls), in Sect. 5 we show that sampling from $\omega_{t}$ achieves the same level of tracking efficiency.

Optimistic primal-dual subgradient descent. At each step $t$, we define an estimated optimistic version of the Lagrangian relaxation (Pλ) as

where $\gamma_{t}$ is a suitable parameter defining the size of the confidence interval.

Notice that we do not use optimism on the context distribution, which is simply replaced by its empirical estimate. Therefore, $h_{t}$ is not necessarily optimistic with respect to the original Lagrangian function $h$. Nonetheless, we prove in Sect. 5 that this level of optimism is sufficient to induce enough exploration to have accurate estimates of $\theta^{\star}$. This is in contrast with the popular forced exploration strategy [e.g. 7, 15, 19, 16], which prescribes a minimum fraction of pulls $\epsilon$ such that at any step $t$, any of the arms with less than $\epsilon S_{t}$ pulls is selected, where $S_{t}$ is the number of exploration rounds so far. While this strategy is sufficient to guarantee a minimum level of accuracy for $\widehat{\theta}_{t}$ and to obtain asymptotic regret optimality, in practice it is highly inefficient as it requires selecting all arms in each context regardless of their value or amount of information.

At each step $t$, SOLID updates the estimates of the optimal exploration policy $\omega_{t}$ and the Lagrangian multiplier $\lambda_{t}$. In particular, given the sub-gradient $q_{t}$ of $h_{t}(\omega_{t},\lambda_{t},z_{K_{t}})$, SOLID updates $\omega_{t}$ and $\lambda_{t}$ by performing one step of projected sub-gradient descent with suitable learning rates $\alpha^{\omega}_{K_{t}}$ and $\alpha^{\lambda}_{K_{t}}$. In the update of $\omega_{t}$, we perform the projection onto the simplex $\Omega$ using an entropic metric, while the multiplier is clipped in $[0,\lambda_{\max}]$. While this is a rather standard primal-dual approach to solve the Lagrangian relaxation (Pλ), the interplay between estimates $\widehat{\theta}_{t}$, $\rho_{t}$, the optimism used in $h_{t}$, and the overall regret performance of the algorithm is at the core of the analysis in Sect. 5.

This approach significantly reduces the computational complexity compared to , which require solving problem P at each exploratory step. In Sect. 6, we show that the incremental nature of SOLID allows it to scale to problems with much larger context-arm spaces. Furthermore, we leverage the convergence rate guarantees of the primal-dual gradient descent to show that the incremental nature of SOLID does not compromise the asymptotic optimality of the algorithm (see Sect. 5).

The $z$ parameter. While the primal-dual algorithm is guaranteed to converge to the solution of (Pz) for any fix $z$, it may be difficult to properly tune $z$ to control the error w.r.t. (P). SOLID leverages the fact that the error scales as $1/\sqrt{z}$ (Lem. 1 for $z$ sufficiently large) and it increases $z$ over time. Given as input two non-decreasing sequences $\{p_{k}\}_{k}$ and $\{z_{k}\}_{k}$, at each phase $k$, SOLID uses $z_{k}$ in the computation of the subgradient of $h_{t}$ and in the definition of $f_{t}$ and $g_{t}$. After $p_{k}$ explorative steps, it resets the policy $\omega_{t}$ and the multiplier $\lambda_{t}$ and transitions to phase $k+1$. Since $p_{k}=S_{T_{k+1}-1}-S_{T_{k}-1}$ is the number of explorative steps of phase $k$ starting at time $T_{k}$, the actual number of steps during $k$ may vary. Notice that at the end of each phase only the optimization variables are reset, while the learning variables (i.e., $\widehat{\theta}_{t}$, $\overline{V}_{t}$, and $\widehat{\rho}_{t}$) use all the samples collected through phases.

Regret Analysis

Before reporting the main theoretical result of the paper, we introduce the following assumption.

The maximum multiplier used by SOLID is such that $\lambda_{\max}\geq 2BL\underline{z}(\theta^{\star})$.

While an assumption on the maximum multiplier is rather standard for the analysis of primal-dual projected subgradient [e.g., 22, 23], we conjecture that it may be actually relaxed in our case by replacing the fixed $\lambda_{\max}$ by an increasing sequence as done for $\{z_{k}\}_{k}$.

Consider a contextual linear bandit problem with contexts $\mathcal{X}$, arms $\mathcal{A}$, reward parameter $\theta^{\star}$, features bounded by $L$, zero-mean Gaussian noise with variance $\sigma^{2}$ and context distribution $\rho$ satisfying Asm. 1. If SOLID is run with confidence values $\beta_{t-1}=c_{n,1/n}$ and $\gamma_{t}=c_{n,1/S_{t}^{2}}$, where $c_{n,\delta}$ is defined as in Thm. 1, learning rates $\alpha_{k}^{\lambda}=\alpha_{k}^{\omega}=1/\sqrt{p_{k}}$ and increasing sequences $z_{k}=z_{0}e^{k}$ and $p_{k}=z_{k}e^{2k}$, for some $z_{0}\geq 1$, then it is asymptotically optimal with the same constant as in the lower bound of Prop. 1. Furthermore, for any finite $n$ the regret of SOLID is bounded as

The sub-logarithmic terms in the regret have only logarithmic dependency on the number of arms. This is better than existing algorithms based on exploration strategies built from lower bounds. OSSB indeed depends on $|\mathcal{A}|$ directly in the main $\mathcal{O}(\log n)$ regret terms. While the regret analysis of OAM is asymptotic, it is possible to identify several lower-order terms depending linearly on $|\mathcal{A}|$. In fact, OAM as well as OSSB require forced exploration on each context-arm pair, which inevitably translates into regret. In this sense, the dependency on $|\mathcal{A}|$ is hard-coded into the algorithm and cannot be improved by a better analysis. SPL depends linearly on $|\mathcal{A}|$ in the explore/exploit threshold (the equivalent of our $\beta_{t}$) and in other lower-order terms due to the analysis of the tracking rule. On the other hand, SOLID never requires all arms to be repeatedly pulled and we were able to remove the linear dependence on $|\mathcal{A}|$ through a refined analysis of the sampling procedure (see App. E). This is inline with the experimental results where we did not notice any explicit linear dependence on $|\mathcal{A}|$.

The constant regret term depends on the context distribution through $\overline{z}(\theta^{\star})$ (Lem. 1). Nonetheless, this dependency disappears whenever $z_{0}$ is a fraction $\overline{z}(\theta^{\star})$. This is in striking contrast with OAM, whose analysis includes several terms depending on the inverse of the context probability $\rho_{\min}$. This confirms that SOLID is able to better adapt to the distribution generating the contexts. While the phase schedule of Thm. 2 leads to an asymptotically-optimal algorithm and sublinear-regret in finite time, it may be possible to find a different schedule having the same asymptotic performance and better finite-time guarantees, although this may depend on the horizon $n$. Refer to App. G.3 for a regret bound highlighting the explicit dependence on the sequences $\{z_{k}\}$ and $\{p_{k}\}$.

Worst-case analysis. The constant terms in Thm. 2 are due to a naive bound which assumes linear regret in those phases where $z_{k}$ is small (e.g., when the optimization problem is infeasible). While this simplifies the analysis for asymptotic optimality, we verify that SOLID always suffers sub-linear regret, regardless of the values of $z_{k}$. For the following result, we do not require Asm. 2 to hold.

Let $z_{k}$ be arbitrary, $p_{k}=e^{rk}$ for some constant $r\geq 1$, and the other parameters be the same as in Thm. 2. Then, for any $n$ the regret of SOLID is bounded as

Notably, this bound removes the dependencies on $\underline{z}(\theta^{\star})$ and $\overline{z}(\theta^{\star})$, while its derivation is agnostic to the values of $z_{k}$. Interestingly, we could set $\lambda_{\max}=0$ and the algorithm would completely ignore the KL constraint, thus focusing only on the objective function. This is reflected in the worst-case bound since all terms with a dependence on $\sigma^{2}$ or a quadratic dependence on $BL$ disappear. The key result is that the objective function alone, thanks to optimism, is sufficient for proving sub-linear regret but not for proving asymptotic optimality. More precisely, the bound is $\widetilde{\mathcal{{O}}}((\sqrt{d}+|\mathcal{X}|)\sqrt{dn}+\log|\mathcal{A}|\sqrt{n})$, which matches the minimax optimal rate apart from the dependence on $|\mathcal{X}|$ (see , Sec. 24.1). We believe the latter could be reduced to $\sqrt{|\mathcal{X}|}$ by a refined analysis. It remains an open question how to design an asymptotically optimal algorithm for the contextual case whose regret does not scale with $|\mathcal{X}|$.

Numerical Simulations

We compare SOLID to LinUCB, LinTS, and OAM. For SOLID, we set $\beta_{t}=\sigma^{2}(\log(t)+d\log\log(n))$ and $\gamma_{t}=\sigma^{2}(\log(S_{t})+d\log\log(n))$ (i.e., we remove all numerical constants) and we use the exponential schedule for phases defined in Thm. 2. For OAM, we use the same $\beta_{t}$ for the explore/exploit test and we try different values for the forced-exploration parameter $\epsilon$. LinUCB uses the confidence intervals from Thm. 2 in with the log-determinant of the design matrix, and LinTS is as defined in but without the extra-sampling factor $\sqrt{d}$ used to prove its frequentist regret. All plots are the results of $100$ runs with $95\%$ Student’s t confidence intervals. See App. K for additional details and results on a real dataset.

Toy contextual linear bandit with structure. We start with a CLB problem with $|\mathcal{X}|=2$ and $|\mathcal{A}|,d=3$. Let $x_{i}$ ($a_{i}$) be the $i$-th context (arm). We have $\phi(x_{1},a_{1})=$, $\phi(x_{1},a_{2})=$, $\phi(x_{1},a_{3})=[1-\xi,2\xi,0]$, $\phi(x_{2},a_{1})=[0,0.6,0.8]$, $\phi(x_{2},a_{2})=$, $\phi(x_{2},a_{3})=[0,\xi/10,1-\xi]$ and $\theta^{\star}=$. We consider a balanced context distribution $\rho(x_{1})=\rho(x_{2})=0.5$. This is a two-context counterpart of the example presented by to show the asymptotic sub-optimality of optimism-based strategies. The intuition is that, for $\xi$ small, an optimistic strategy pulls $a_{2}$ in $x_{1}$ and $a_{1}$ in $x_{2}$ only a few times since their gap is quite large, and suffers high regret (inversely proportional to $\xi$) to figure out which of the remaining arms is optimal. On the other hand, an asymptotically optimal strategy allocates more pulls to “bad" arms as they bring information to identify $\theta^{\star}$, which in turns avoids a regret scaling with $\xi$. This indeed translates into the empirical performance reported in Fig. 1-(left), where SOLID effectively exploits the structure of the problem and significantly reduces the regret compared to LinTS and LinUCB. Actually, not only the regret is smaller but the “trend” is better. In fact, the regret curves of LinUCB and LinTS have a larger slope than SOLID’s, suggesting that the gap may increase further with $n$, thus confirming the theoretical finding that the asymptotic performance of SOLID is better. OAM has a similar behavior, but the actual performance is worse than SOLID and it seems to be very sensitive to the forced exploration parameter, where the best performance is obtained for $\epsilon=0.0$, which is not theoretically justified.

We also study the influence of the context distribution. We first notice that solving (P) leads to an optimal exploration strategy $\eta^{\star}$ where the only sub-optimal arm with non-zero pulls is $a_{1}$ in $x_{2}$ since it yields lower regret and similar information than $a_{2}$ in $x_{1}$. This means that the lower bound prescribes a greedy policy in $x_{1}$, deferring exploration to $x_{2}$ alone. In practice, tracking this optimal allocation might lead to poor finite-time performance when the context distribution is unbalanced towards $x_{1}$, in which case the algorithm would take time proportional to $1/\rho(x_{2})$ before performing any meaningful exploration. We verify these intuitions empirically by considering the case of $\rho(x_{1})=0.9$ and $\rho(x_{1})=0.99$ (middle and right plots in Fig. 1 respectively). SOLID is consistently better than all other algorithms, showing that its performance is not negatively affected by $\rho_{\min}$. On the other hand, OAM is more severely affected by the context distribution. In particular, its performance with $\epsilon=0$ significantly decreases when increasing $\rho(x_{1})$ and the algorithm reduces to an almost greedy strategy, thus suffering linear regret in some problems. In this specific case, forcing exploration leads to slightly better finite-time performance since the algorithm pulls the informative arm $a_{2}$ in $x_{1}$, which is however not prescribed by the lower bound.

Random problems. We evaluate the impact of the number of actions $|\mathcal{A}|$ in randomly generated structured problems with $d=8$ and $|\mathcal{X}|=4$. We run each algorithm for $n=50000$ steps. For OAM, we set forced-exploration $\epsilon=0.01$ and solve (P) every $100$ rounds to speed-up execution as computation becomes prohibitive. The plots in Fig. 2 show the regret over time for $|\mathcal{A}|=4,8,16,32$. This test confirms the advantage of SOLID over the other methods. Interestingly, the regret of SOLID does not seem to significantly increase as a function of $|\mathcal{A}|$, thus supporting its theoretical analysis. On the other hand, the regret of OAM scales poorly with $|\mathcal{A}|$ since forced exploration pulls all arms in a round robin fashion.

Conclusion

We introduced SOLID, a novel asymptotically-optimal algorithm for contextual linear bandits with finite-time regret and computational complexity improving over similar methods and better empirical performance w.r.t. state-of-the-art algorithms in our experiments. The main open question is whether SOLID is minimax optimal for contextual problems with $|\mathcal{X}|>\sqrt{d}$. In future work, our method could be extended to continuous contexts, which would probably require a reformulation of the lower bound and the adoption of parametrized policies. Furthermore, it would be interesting to study finite-time lower bounds, especially for problems in which bounded regret is achievable . Finally, we could use algorithmic ideas similar to SOLID to go beyond the realizable linear bandit setting.

Broader Impact

This work is mainly a theoretical contribution. We believe it does not present any foreseeable societal consequence.

Funding Transparency Statement

Marcello Restelli was partially funded by the Italian MIUR PRIN 2017 Project ALGADIMAR “Algorithms, Games, and Digital Market”.

Acknowledgements

The authors would like to thank Rémy Degenne, Han Shao, and Wouter Koolen for kindly sharing the draft of their paper before publication. We also would like to thank Pierre Ménard for carefully reading the paper and for providing insightful feedback.

References

Appendix

We provide this table for easy reference. Notation will also be defined as it is introduced.

Appendix B Comparison to Related Work

In Table 2 we compare several bandit algorithms along several dimensions:

Setting refers to whether the algorithm is designed for general multi-armed bandit (non-contextual) structured problems or it is for the linear contextual case.

Objective function refers to the optimization problem solved by the algorithm. It can be either the original constrained optimization in (P) or a saddle point problem (either obtained by taking the ratio of objective and constraints or the Lagrangian relaxation in (Pz)).

Optimization variables refers to the variables that are optimized by the algorithm: counts is the $\eta$ variables in (P), rates is the ratio fraction of regret, policies is the $\omega$ variables in (Pz).

Asymptotic optimality is either order optimal when only a logarithmic rate is proved with non-optimal constants, or optimal, in which case the leading constant is $v^{\star}(\theta)$ as in Prop. 1.

Finite-time bound is whether finite-time guarantees are reported.

Explore/exploit refers to the separation between exploration and exploitation steps and whether it is based on a tracking performance test or on the generalized likelihood ratio test (GLRT).Notice that none of the algorithms implement the exact form of the GLRT, but slight variations that provide equivalent guarantees.

Tracking refers to how arms are selected during the exploration phase.

Optimization refers to whether the optimization problem is solved exactly at each step or using an incremental method. SPL combines an incremental method using an exact computation of a best response solution.

Exploration level refers to the technique used during exploration steps to guarantee a minimum level of exploration. The first option is forcing all arms to satisfy a hard threshold of minimal pulls. The second option is to include a form of optimism in the optimization problem.

Parameters list the major parameters in the definition of the algorithm. This is often difficult since some algorithms directly pick theoretical values for some input parameters, while others may provide specific values only during the analysis. OSSB requires tuning the forcing parameter and the parameter used in the exploration/exploitation test. OAM has a forcing parameter and needs to properly tune the GLRT. SPL requires clipping the gap estimates from below, tuning the GLRT, and designing suitable confidence intervals for optimism. SOLID requires an upper bound for the multiplier, tuning of the GLRT, confidence intervals, and phases to tune the normalization factor $z$.

The major insights from this comparison can be summarized as follows:

Comparison SOLID/OAM: This is the more direct comparison, since both algorithms are designed for contextual linear (see Sect. 6 for the empirical comparison). SOLID improves over OAM in almost all dimensions. On the theoretical side, we provide explicit finite-time regret bounds showing that SOLID successfully adapts to the context distribution, while the performance of OAM is significantly affected by $\rho_{\min}$. Furthermore, in many lower-order regret terms in the analysis of OAM the cardinality of the arm space appears linearly, while the regret of SOLID only depends on $\log(|\mathcal{A}|)$. On the algorithmic side, SOLID leverages a primal-dual gradient descent that greatly improves the computational complexity compared to the exact solution of the constrained optimization problem done in OAM at each exploration step. Furthermore, replacing the forcing strategy with an optimistic version of the optimization problem allows SOLID to better adapt to the problem and avoid pulling highly suboptimal/non-informative arms.

Comparison SOLID/SPL: The comparison is more on the algorithmic and theoretical properties rather than the actual algorithms, since they are designed for different settings.While the general structured bandit problem does contain the linear case, it is unclear how it can manage the contextual linear case. While both algorithms replace the constrained problem in the lower bound by a saddle point problem, SPL takes the ratio between constraints and regret, while in SOLID we take a more straightforward Lagrangian relaxation. As a result, in SOLID we rely on a rather standard primal-dual gradient approach to optimize (Pz), while SPL relies on online learning algorithms for the solution of the saddle-point problem. Finally, both algorithms replace forcing by an optimistic version of the optimization problem. Nonetheless, SPL uses separate confidence intervals for each arm that ignore the structure of the problem, while SOLID relies on confidence intervals build specifically for the linear case. Finally, the regret bound of SPL, similarly to the one of OAM, depends linearly on $|\mathcal{A}|$ in several lower-order terms, even when instantiated for linear structures. SOLID, on the other hand, has only $\log(|\mathcal{A}|)$ dependence.

Appendix C Lower Bound

We start from the first result in Lem. 1, which states the minimal value of $z$ for which (Pz) is feasible. Clearly, the maximal value that the left-hand side of the KL constraint can assume is

which can also be interpreted as the solution to the associated pure-exploration (or best-arm identification) problem [e.g., 18]. Therefore,

This proves the first statement in Lem. 1.

In order to prove the second result, let us rewrite (Pz) in the following more convenient form:

Note that ($\text{P}^{\prime}_{z}$) is obtained from (Pz) in the main paper by performing the change of variables $\eta(x,a)=z\omega(x,a)$, hence the two problems are equivalent. Recall that $v^{\star}(\theta^{\star})$ is the optimal value of (P) and $u^{\star}(z,\theta^{\star})$ is the optimal value of ($\text{P}^{\prime}_{z}$) and (Pz) (if there exists one). We are interested in bounding the deviation between $u^{\star}(z,\theta^{\star})$ and $v^{\star}(\theta^{\star})$ as a function of $z$.

Let us first define the following set of confusing models:

We now prove the bound on $u^{\star}(z,\theta)$ reported in Lem. 1.

We start from the Lagrangian version of ($\text{P}^{\prime}_{z}$).

subject to $\sum_{a\in\mathcal{A}}\eta(x,a)=z$ for each context $x\in\mathcal{X}$. Here $\lambda^{\star}(z,\theta^{\star})$ is the optimal value of the Lagrange multiplier for the same problem. We distinguish two cases.

where $\eta^{\star}$ is the optimal solution of (P). Since $\sum_{a}\overline{\eta}(x,a)=z$, we have that $u^{\star}(z,\theta^{\star})$ is less or equal to the value of the Lagrangian for $\eta=\overline{\eta}$, i.e.,

since $\Delta_{\theta^{\star}}(x,a^{\star}_{\theta^{\star}}(x))=0$. Since the KL divergence $d_{x,a}(\theta^{\star},\theta^{\prime})$ is lower-bounded by zero, in case 1 we have

where, as before, $\eta^{\star}$ is the optimal solution of (P). Since $z\geq\sum_{a\neq a^{\star}_{\theta^{\star}}(x)}\eta^{\star}(x,a)/\rho(x)$ for any $x\in\mathcal{X}$, $\overline{\eta}$ is well defined. Since $\overline{\eta}$ also sums to $z$ for each context, we have that $u^{\star}(z,\theta)$ is less or equal to the value of the Lagrangian for $\eta=\overline{\eta}$, i.e.,

We first lower bound the infimum on the right hand side. We have

By definition of $\overline{\eta}$ and $\eta^{\star}$, the infimum over the set of confusing models can be written as

where the equality holds since the KLs are zero in the optimal arms, which are the only arms where the values of $\overline{\eta}$ differ from those of $\eta^{\star}$, and the inequality holds since $\eta^{\star}$ is feasible. Regarding the infimum over the non-confusing models,

We partition the set of non-confusing models in two subsets:

Setting $\epsilon_{z}=\sqrt{\frac{2\sigma^{2}}{z}}$,

Finally, we show that the optimal multiplier $\lambda^{\star}(z,\theta^{\star})$ is bounded (regardless of which case $z$ falls into). Let $\underline{\eta}=z\underline{\omega}$, where $\underline{\omega}=\omega^{\star}_{\underline{z},\theta^{\star}}$ is the pure-exploration solution obtained solving problem (Pz) with $\underline{z}(\theta^{\star})$. Recall from the first statement of Lem. 1 that

since $z>\underline{z}(\theta^{\star})$ by assumption. Using the Slater’s condition (see e.g., Lem. 3 in ),

C.2 Discussion About Problem (Pz)

In this section we provide more intuition about the effect of explicitly adding the context distribution in the formulation of the lower bound. As mentioned in Sect. 3 the infimum in the original problem (P) may not be attainable, thus making it difficult to solve it and build a learning algorithm around it. A simple way to address this issue is to introduce a global constraint so that the sum of $\eta$ is constrained to a parameter $z$. This leads to the optimization

Let $\widetilde{\eta}^{\star}_{z}$ be the optimal solution of ($\widetilde{P}_{z}$) and $\widetilde{u}^{\star}_{z}$ be its associated optimal value. On the other hand, the problem (Pz) we propose can be easily rewritten as

where the constraint is now on each context and it depends on the context distribution ($\omega(x,a)=\frac{\eta(x,a)}{z\rho(x)}$).Notice that the constraint directly implies $\sum_{x,a}\eta(x,a)=z$. The crucial difference w.r.t. ($\widetilde{P}_{z}$) is that now the number of samples prescribed by $\eta$ needs to be “compatible” with the amount of samples that can be collected within $z$ steps from each context $x$ depending on its probability $\rho(x)$. Let $\eta^{\star}_{z}$ be the optimal solution of ($P_{z}$) and $u^{\star}_{z}$ be its associated objective value. In order to understand how this difference may translate into a different behavior when integrated in an actual algorithm, let compare the two solutions $\widetilde{\eta}^{\star}_{z}$ and $\eta^{\star}_{z}$ if executed for $z$ steps.We recall that, as discussed in Sect. 3, $z$ introduces a more finite-time flavor into the lower bound, where pulls should now be allocated so as to satisfy the KL-information constraint within $z$ steps. Since neither of them can be “played” (i.e., only one arm can be selected at each step), we need to define a specific execution strategy to “realize” an allocation $\eta$. For the ease of exposition, let consider a simple strategy where in each context $x$, an arm $a$ is pulled at random proportionally to $\eta(x,a)$. Let $\widetilde{\zeta}_{z}(x,a)$ and $\zeta_{z}(x,a)$ the expected number of samples generated in each context-arm pair $(x,a)$ when sampling from $\widetilde{\eta}^{\star}_{z}$ and $\eta^{\star}_{z}$ respectively. Then we have

which reveals how $\widetilde{\eta}^{\star}_{z}(x,a)$, which was explicitly optimized under the constraint that the total number of samples was $z$, may not really be “realizable” in practice, since it ignores the context distribution and the number of samples that can be actually generated at each context $x$. On the other hand, on average the desired allocation $\eta^{\star}_{z}$ can always be realized within $z$ steps. Interestingly, the mismatch between $\widetilde{\eta}^{\star}_{z}(x,a)$ and $\widetilde{\zeta}_{z}(x,a)$ would no longer guarantee neither the performance $\widetilde{u}^{\star}_{z}$ “promised” by $\widetilde{\eta}^{\star}_{z}$ nor the feasibility for ($\widetilde{P}_{z}$) (i.e., $\widetilde{\zeta}_{z}(x,a)$ may not satisfy the KL-information constraint). This would make considerably more difficult to build a learning algorithm on $\widetilde{\eta}^{\star}_{z}$ than on $\eta^{\star}_{z}$.

As it can be noticed in Eq. 26, the level mismatch is due to the execution strategy used to realize the allocation $\widetilde{\eta}^{\star}_{z}$ (in this case, a simple sampling approach) and better solutions may exist. We could even consider to directly optimize the execution strategy so as to achieve a mismatch $\alpha_{z}(x,a)$ that induce an allocation $\widetilde{\zeta}_{z}(x,a)$ that performs best in terms of regret minimization under the KL-information constraint. Given the $\widetilde{\eta}^{\star}_{z}$ obtained from ($\widetilde{P}_{z}$), we define the optimization problem

Interestingly, a simple change of variables reveals that ($\widetilde{P}_{\alpha}$) does coincide with ($P_{z}$) that we originally introduced (i.e., $\alpha^{\star}(x,a)=\frac{\eta^{\star}_{z}(x,a)}{\widetilde{\eta}^{\star}_{z}(x,a)}$ minimizes the problem). This illustrates that solving ($P_{z}$) indeed leads to the optimal allocation compatible with the context distribution and the constraint of $z$ realizations.

Appendix D Lagrangian Formulation

We discuss in more details the Lagrangian formulation presented in Section 3. Consider the following variant of (Pz):

This problem differs from (Pz) since we replaced the action gaps with the means in the objective function and avoided scaling the latter by $z$. Let $\overline{\omega}^{\star}_{z,\theta^{\star}}$ the optimal solution of ($\overline{P}_{z}$) and $\overline{u}^{\star}(z,\theta^{\star})$ be its associated value (if the problem is unfeasible we set $\overline{u}^{\star}(z,\theta^{\star})=+\infty$). Since the feasibility set is equivalent in (Pz) and ($\overline{P}_{z}$) as we only changed the objective function, the following proposition is immediate.

Both (Pz) and ($\overline{P}_{z}$) are feasible for $z\geq\underline{z}(\theta^{\star})$;

${\omega}^{\star}_{z,\theta^{\star}}=\overline{\omega}^{\star}_{z,\theta^{\star}}$.

Due to the equivalence demonstrated in Prop. 3, in the remaining we shall occasionally write $\omega^{\star}_{z}$ to denote both ${\omega}^{\star}_{z,\theta^{\star}}$ and $\overline{\omega}^{\star}_{z,\theta^{\star}}$.

We recall the Lagrangian relaxation problem of Sec. 3. For any $\omega\in\Omega$, let $f(\omega;\theta^{\star})$ denote the objective function and $g(\omega,z;\theta^{\star})$ denote the KL constraint

The Lagrangian relaxation problem of ($\overline{P}_{z}$) isIn the main text we actually state that (Pλ) is the Lagrangian relaxation of (Pz) instead of ($\overline{P}_{z}$). This is motivated by the fact that (Pλ) and (Pz) have the same optimal solution (see Prop. 3), though different optimal objective values.

We now verify that strong duality holds for the Lagrangian formulation (Pλ) (with respect to ($\overline{P}_{z}$)) when $z>\underline{z}(\theta^{\star})$. This is immediate from the existence of a Slater point, as shown in the following proposition.

For any $z>\underline{z}(\theta^{\star})$, there exists a strictly feasible solution $\underline{\omega}$, i.e., $g(\underline{\omega};z,\theta^{\star})>0$.

This is a direct consequence of the fact that

Thus, the optimal solution of (Pλ) is $\left(\lambda^{\star}(z,\theta^{\star}),\omega^{\star}_{z}\right)$.

For any $z>\underline{z}(\theta^{\star})$, if $\overline{\omega}_{z}$ is a Slater point for ($\overline{P}_{z}$),

Using Lemma 2, we can prove the following result which will be very useful for the regret analysis.

For any $z\geq 2\underline{z}(\theta^{\star})$,

From Prop. 4, $\underline{\omega}$ (the solution of the associated pure-exploration problem) is a Slater point for problem (Pz). Then, by Lemma 2,

where the last inequality holds for $z\geq 2\underline{z}(\theta^{\star})$. This concludes the proof. ∎

Appendix E Action Sampling

SOLID does not use standard tracking approaches for action selection (e.g., cumulative tracking or direct tracking ) but a sampling strategy. Despite being simpler and more practical than tracking, we show that sampling from $\omega_{t}$ enjoys nice theoretical guarantees.

In the following lemmas we define the filtration $\mathcal{F}_{t}$ as the $\sigma$-algebra generated by the $t$-step history, $H_{t}=(X_{1},A_{1},Y_{1},\dots,X_{t},A_{t},Y_{t})$.

Let $\{\omega_{t}\}_{t\geq 1}$ be such that $\omega_{t}\in\Omega$ and $\omega_{t}$ is $\mathcal{F}_{t-1}$-measurable. Let $\{X_{t}\}_{t\geq 1}$ be a sequence of i.i.d. contexts distributed according to $\rho$ and $\{A_{t}\}_{t\geq 1}$ be such that $A_{t}\sim\omega_{t}(X_{t},\cdot)$. Then,

Let $Z_{t}:=\mathds{1}\left\{X_{t}=x,A_{t}=a\right\}$ and $\tau_{s}$ be a random variable such that the $s$-th exploration round occurs at time $\tau_{s}+1$. Notice that $\{\tau_{s}\}_{s\geq 1}$ is a strictly-increasing sequence (i.e., $\tau_{s+1}>\tau_{s}$) of stopping times w.r.t. $\{\mathcal{F}_{t}\}_{t\geq 1}$. Furthermore, define

and let $\mathcal{G}_{s}:=\mathcal{F}_{\tau_{s+1}}$. Using Lem. 10 in , we have that $\{W_{s},\mathcal{G}_{s}\}_{s\geq 1}$ is a martingale difference sequence. Therefore, by Azuma’s inequality

Let $a_{t}:=\sqrt{\frac{S_{t}}{2}\log\left(S_{t}^{2}|\mathcal{X}||\mathcal{A}|\right)}$ and rewrite $N_{t}^{E}(x,a)=\sum_{s\leq t:E_{s}}Z_{s}$. Fix any $\overline{t}\geq 1$. Then,

In the last inequality, we used the fact that $a_{\tau_{s}+1}=\sqrt{s\log s}$. Taking expectations and applying Azuma’s inequality with $\delta=\frac{2}{s^{2}|\mathcal{X}||\mathcal{A}|}$,

The results holds for all $\overline{t}$, and the proof is concluded by summing over contexts and arms. ∎

Let $\{\omega_{t}\}_{t\geq 1}$ be such that $\omega_{t}\in\Omega$ and $\omega_{t}$ is $\mathcal{F}_{t-1}$-measurable. Let $\{X_{t}\}_{t\geq 1}$ be a sequence of i.i.d. contexts distributed according to $\rho$ and $\{A_{t}\}_{t\geq 1}$ be such that $A_{t}\sim\omega_{t}(X_{t},\cdot)$. Let $\{\varphi_{t}^{i}\}_{t\geq 1,i\in[m]}$ be a sequence of functions $\varphi_{t}^{i}:\mathcal{X}\times\mathcal{A}\rightarrow[-b,b]$ such that $\varphi_{t}^{i}(x,a)$ is $\mathcal{F}_{t-1}$-measurable for all $i\in[m]$. Then,

The proof follows the same steps as the one of Lemma 4. Fix $i\in[m]$. Let $Z_{t}:=\varphi_{t}^{i}(X_{t},A_{t})$ and $\tau_{s}$ be a random variable such that the $s$-th exploration round occurs at time $\tau_{s}+1$. Notice that $\{\tau_{s}\}_{s\geq 1}$ is a strictly-increasing sequence (i.e., $\tau_{s+1}>\tau_{s}$) of stopping times w.r.t. $\{\mathcal{F}_{t}\}_{t\geq 1}$. Furthermore, define

and let $\mathcal{G}_{s}:=\mathcal{F}_{\tau_{s+1}}$. Using Lem. 10 in , we have that $\{W_{s},\mathcal{G}_{s}\}_{s\geq 1}$ is a martingale difference sequence (with differences bounded by $b$). Therefore, by Azuma’s inequality

Let $a_{t}:=b\sqrt{\frac{S_{t}}{2}\log\left(mS_{t}^{2}\right)}$ and fix some $\bar{t}\geq 1$. Then,

In the last inequality, we used the fact that $a_{\tau_{s}+1}=b\sqrt{\frac{s}{2}\log(ms^{2})}$. Taking expectations and applying Azuma’s inequality with $\delta=\frac{2}{ms^{2}}$,

The results holds for all $\bar{t}$ and the proof follows by summing over all $i\in[m]$. ∎

Lemma 4 provides an analogous result to those obtained by tracking strategies, where the empirical pull counts are shown close to the sequence of conditional probabilities computed by the optimizer. Despite being simpler, our sampling rule achieves similar efficiency as existing tracking rules. In particular, our bound scales with $\log|\mathcal{A}|$, a factor that appears in the tightest known analysis of cumulative tracking . The factor $\sqrt{S_{t}\log S_{t}}$ is not typically found in tracking strategies for MABs. However, we note that such dependency would naturally appear when generalizing these strategies to the contextual case.

Lemma 5 extends Lemma 4 to bound the deviation between expectations of measurable functions under the sequence of conditional probabilities and the same functions evaluated at the observed contexts/arms. This result will be very useful in the regret analysis to avoid undesirable linear dependencies on the number of arms.

Appendix F High-Probability Events

In this section, we report the high-probability events used through the paper. Refer to App. I.1 for concentration inequalities.

Let $\Phi_{x,a}:=\phi(x,a)\phi(x,a)^{T}$. We define the following events:

Furthermore, we define $G_{t}:=\{G_{t}^{\Delta},G_{t}^{\phi},G_{t}^{d},,G_{t}^{\rho},G_{t}^{\theta}\}$ as the “good” event and let $M_{t}=\sum_{s=1}^{t}\mathds{1}\left\{E_{s},\neg G_{s}\right\}$ be the number of exploration rounds in which the good event does not hold. This can be bounded in expectation as follows.

Let $M_{t}=\sum_{s=1}^{t}\mathds{1}\left\{E_{s},\neg G_{s}\right\}$ be the number of exploration rounds in which the good event does not hold, then

Using the definition of $G_{s}$ together with the union bound,

The first and second term can be bounded by Lemma 5 by noticing that $\Delta_{\theta^{\star}}(x,a)\leq 2LB$ and that $\|\phi(x,a)\|_{\bar{V}_{s-1}^{-1}}$ is $\mathcal{F}_{s-1}$-measurable and upper-bounded by $\frac{L}{\nu}$ at all time steps. Thus,

Similarly, the third term can be bounded by Lemma 5 by taking a union bound over all elements of $\Phi_{x,a}$ (for a total of $d^{2}$ elements) and noting that each term is bounded by $L^{2}$. Thus,

Here we used the fact that the absolute difference between two consecutive empirical means with samples bounded by $1$ cannot be larger than $\frac{2}{s}$. We also used Lemma 7 to bound the second term. Finally, the fifth term can be directly bounded by Lemma 8:

Combining the five bounds concludes the proof. ∎

Appendix G Regret Proof

We start decomposing the regret based on whether $E_{t}$ holds or not:

Throughout the proof, as stated in the main theorem, we use $\beta_{t-1}:=c_{n,1/n}$ and $\gamma_{t}:=c_{n,1/S_{t}^{2}}$.

(App. G.2) Using the confidence set derived in App. J, we show that the regret suffered when the algorithm enters the exploitation step is finite;

(App. G.3.1) Using the properties of our action sampling strategy, we reduce the regret incurred during exploration rounds to the sum of objective values of the policies computed incrementally by primal-dual gradient ascent;

(App. G.3.2) By combining standard tools from convex optimization with the properties of our confidence intervals, we relate the sum of objective values at each phase to the corresponding optimal value and constraint violations;

(App. G.3.3) We relate the sum of constraints to the exploitation test used by SOLID. In particular, using the fact that the algorithm is not in the exploitation step, we show that the sum of constraints cannot be larger than $\mathcal{O}(\log n)$;

(App. G.3.5) By relating the upper bound on the sum of constraints computed at Step 3 and a lower bound on the same quantity, we obtain an upper bound on $K_{n}$ as a function of the chosen sequences $p_{k},z_{k}$;

(App. G.3.6) We derive the final result by combining the bound on $K_{n}$ of Step 5 using the exponential schedule for $p_{k},z_{k}$ with the partial regret bound of Step 4.

G.2 Regret during Exploitation

We show that the regret suffered when exploitation occurs is finite. Let $\beta_{t-1}:=c_{n,1/n}$, where $c_{n,\delta}$ was defined in Thm. 1. Then $F_{t}:=\mathds{1}\left\{\|\widehat{\theta}_{t-1}-\theta^{\star}\|_{\overline{V}_{t-1}}^{2}\leq c_{n,1/n}\right\}$ is the event under which the true model belongs to the confidence set, which holds with probability at least $1-1/n$ by the same theorem. We leverage this to decompose the regret during exploitation as:

The expectation of the second term is bounded by

where the first inequality is due to the fact that the good event $F_{t}$ holds and Cor. 1. This is a contradiction with respect to $F_{t}$. Therefore, $\neg E_{t}$ and $F_{t}$ cannot hold at the same time and the algorithm suffers no regret. Combining these results, we conclude

G.3 Regret under Exploration

The key challenge is to bound the regret during the exploration rounds. We proceed by following the steps outlined in App. G.1.

We decompose the regret incurred during exploration as

Refer to App. F for the definition of $G_{t}$. The second term is $M_{n}$, the number of exploration rounds in which the good event does not hold, and can be bounded in expectation by using Lem. 6. The first one can be bounded by using the good event. Suppose, without loss of generality, that $E_{n}$ and $G_{n}$ hold (if they do not, the following reasoning can be repeated for the last time step at which these events hold). Then, using $G_{t}^{\Delta}$ (see App. F),

Using the definition of phase, we can rewrite the first summation as

which yields at most finite regret since $\{p_{k}\}$ is increasing. Let us now fix a phase $k\geq\underline{k}$ and bound the regret during its exploration rounds ($\mathcal{T}_{k}^{E}$). Note that the optimization problem in each phase $k\geq\underline{k}$ is feasible (see App. D). We have

Here we defined $\mu^{\star}:=\sum_{x\in\mathcal{X}}\rho(x)\mu^{\star}_{\theta^{\star}}(x)$ and $M_{n,k}$ as the number of exploration rounds during phase $k$ where the good event does not hold. The last term can be bounded by $M_{n,k}BL$. Regarding the remaining two,

The second term $\zeta_{n,k}$ will be bounded shortly over all phases by means of Lemma 12. We now provide a lower bound to term (b). The first step is to relate this to the objective function optimized by the algorithm. Using the definition of $G_{t}$ and Lem. 10,

In the last step, we used $\sqrt{\gamma_{t}}\leq\sqrt{\gamma_{n}}$ (which is by definition $\mathcal{O}(\log S_{n})$) and defined $\Psi_{n,k}:=\sum_{t\in\mathcal{T}_{k}^{E}}\sum_{x\in\mathcal{X}}\hat{\rho}_{t-1}(x)\sum_{a\in\mathcal{A}}\omega_{t}(x,a)\|\phi(x,a)\|_{\bar{V}_{t-1}^{-1}}$.

To wrap-up the regret bound we have obtained so far, summing over all phases,

$\zeta_{n}$ can be bounded by Lemma 12 and $\Psi_{n}$ by Lemma 13. Both terms are of order $\mathcal{O}(\sqrt{S_{n}\log S_{n}})$. In order to simplify notation, we keep the specific bounds implicit in the remaining. Therefore, our partial regret bound is

Our goal here is to lower bound the sum of objective values. As before, fix some phase index $k\geq\underline{k}$ and let $\lambda\geq 0$ be arbitrary. By recalling that the optimization process is reset at the beginning of each phase and using Corollary 2 with $\alpha_{k}^{\lambda}=\alpha_{k}^{\omega}=1/\sqrt{p_{k}}$ and $\omega=\omega^{\star}_{z_{k}}$ (the optimal solution of problem (P${}_{z_{k}}$)),

We recall that $b_{\lambda}$ and $b_{\omega}$ are the maximum sub-gradients in $\lambda$ and $\omega$, respectively. We now lower-bound the first term on the right-hand side. Since $h_{t}(\omega^{\star}_{z_{k}},\lambda_{t},z_{k})=f_{t}(\omega^{\star}_{z_{k}})+\lambda_{t}g_{t}(\omega^{\star}_{z_{k}},z_{k})$, $f_{t}(\omega^{\star}_{z_{k}})\geq-LB$, $g_{t}(\omega^{\star}_{z_{k}},z_{k})\geq-\frac{1}{z_{k}}$, and $\lambda_{t}\leq\lambda_{\max}$, this term, evaluated on those steps where $G_{t}$ does not hold, can be lower-bounded by $\sum_{t\in\mathcal{T}_{k}^{E}:\neg G_{t}}h_{t}(\omega^{\star}_{z_{k}},\lambda_{t},z_{k})\geq-(LB+\lambda_{\max}/z_{k})M_{n,k}$. For any step $t\in\mathcal{T}_{k}^{E}$ in which $G_{t}$ holds, the optimism property (Lemma 11) yields

Combining these two and using $\lambda_{t}\leq\lambda_{\max}$,

Note that $g(\omega^{\star}_{z_{k}})\geq 0$ since by assumption $\omega^{\star}_{z_{k}}$ is feasible for the optimization problem $(P_{z_{k}})$. Furthermore, $\sum_{t\in\mathcal{T}_{k}^{E}:G_{t}}f(\omega^{\star}_{z_{k}})=\sum_{t\in\mathcal{T}_{k}^{E}}f(\omega^{\star}_{z_{k}})-\sum_{t\in\mathcal{T}_{k}^{E}:\neg G_{t}}\underbrace{f(\omega^{\star}_{z_{k}})}_{|\cdot|\leq LB}\geq p_{k}f(\omega^{\star}_{z_{k}})-LBM_{n,k}$. Therefore, we obtain the following lower-bound on the sum of optimal objective values:

where, for simplicity, we defined $a_{\lambda}:=\left(\log|\mathcal{A}|+\frac{b_{\omega}^{2}+b_{\lambda}^{2}}{2}+\frac{(\lambda-\lambda_{1})^{2}}{2}\right)$. Summing over all phases,

where we used $\sum_{k\geq\underline{k}}^{K_{n}}M_{n,k}\leq M_{n}$, $\sum_{k\geq\underline{k}}^{K_{n}}\zeta_{n,k}\leq\zeta_{n}$, and $z_{k}\geq 1$.

Our next step is to upper bound $\sum_{k\geq\underline{k}}^{K_{n}}\sum_{t\in\mathcal{T}_{k}^{E}}g_{t}(\omega_{t},z_{k})$, the sum of constraints of the policies played by the algorithm during feasible phases (those with $z_{k}\geq 2\underline{z}(\theta^{\star})$). The intuition is that this term cannot be large (i.e., it cannot be above $\mathcal{O}(\log n)$), otherwise the exploitation test would trigger and we would not be exploring at step $n$. Using the definition of $g_{t}(\omega,z_{k})$ (Eq. 3) and splitting the sum based on the good event

Note that in the first step above we implicitly upper bounded the sum of KLs on the feasible phases with the sum of KLs over all exploration rounds. We can use the definition of $G_{t}$ and the optimism (Lemma 11) to upper bound the first sum by

Furthermore, the first term can be upper bounded by replacing each set $\bar{\Theta}_{t-1}$ over which the infimum is taken by ${\Theta}_{alt}$ (if the two sets were different, such term would be zero). Therefore,

where we moved the infimum outside the outer sum and added the remaining steps where $G_{t}$ does not hold. Let $\Phi_{x,a}:=\phi(x,a)\phi(x,a)^{T}$ and $V_{n,e}:=\sum_{t\leq n:E_{t}}\Phi_{X_{t},A_{t}}$ be the design matrix of the exploration rounds. Using the definition of $d_{x,a}$,

Recall that $G_{n}$ holds. Then, by using the definition of $G^{d}$ to bound the norm,

Here we used $N_{n}(x,a)=N_{n-1}(x,a)+\mathds{1}\left\{X_{n}=x,A_{n}=a\right\}$ and upper bounded the KL at round $n$ by its maximum value. Moreover, similarly to Lem. 11 we can show that

The upper bound on the second term can be extracted from the proof of Lemma 13. The first term can be finally related to the exploitation test:

where the second-last inequality holds since $\bar{V}_{n-1}\succeq V_{n-1}$, and the last inequality holds since the algorithm is exploring at step $n$. By gathering all the results together, we get

So far we have (1) reduced the total regret during exploration to the sum of objective values (Eq. G.3.1), (2) related this quantity to the optimal values of each phase (Eq. 40), and (3) derived an upper bound to the total sum of constraints (Eq. 42). We now combine all these results. If we first plug (40) into (G.3.1),

Then, plugging (42) into this inequality,

Let us simplify this expression so that it becomes more readable. First, we note that

Taking the expectation of both sides, we obtain

The remaining expectations on the right-hand side are due to the fact that $K_{n}$ (hence $S_{n}$) is still random. Setting $\lambda=v^{\star}(\theta^{\star})$ and combining the second and fourth terms, we get

where $\bar{z}(\theta^{\star}):=\max_{x\in\mathcal{X}}\sum_{a\neq a^{\star}_{\theta^{\star}}(x)}\frac{\eta^{\star}(x,a)}{\rho(x)}$ was defined in Lem. 1. For $k\geq\underline{k}$, we can use the perturbation bound (Lem. 1) on both terms. We obtain,

Plugging these bounds into the expected regret,

The six terms constituting the bound are (from left to right):

finite regret suffered in the phases where the optimization problem is infeasible;

finite regret suffered in the phases in which we do not know much about the convergence rate of $u^{\star}(z,\theta^{\star})$ to $v^{\star}(\theta^{\star})$. This term is likely an artefact of the analysis;

regret suffered due to the incremental gradient updates and inversely proportional to the step sizes;

regret suffered due to the fact that we solve (Pz) instead of (P);

other low-order terms mostly due to the concentration bounds.

Note that, since $\beta_{n-1}=c_{n,1/n}$ and $c_{n,1/n}\rightarrow 2\sigma^{2}\log n$ as $n\rightarrow\infty$,

which is the asymptotically-optimal regret rate as prescribed by (P).

So far we proved an upper bound on the regret incurred during exploration which depends on the (random) number of phases. We now upper bound this random variable as a function of $z_{k}$ and $p_{k}$. In particular, we achieve this by focusing on the constraints only. The intuition is that, if the primal-dual algorithm works, then the sequence of policies played cannot violate the constraints at each phase too much. At the same time, these policies cannot satisfy the constraints too much, otherwise the exploitation test would trigger and the algorithm would not be exploring at step $n$. Relating these two we obtain a bound on $K_{n}$.

Recall that, as we assumed before, $n$ is an exploration step in which the good event $G_{n}$ holds. Using (G.3.3) and the equations thereafter, we have

where the last two terms are $\mathcal{O}(\sqrt{S_{n}\log S_{n}})$.

We now provide a lower-bound on the same quantity. Fix a phase index $k\geq\underline{k}$. From (39), we have

The left-hand side can be upper-bounded by using the optimism property to obtain the true objective and constraint. Regarding the objective function, we have

Regarding the sum over the good events, using Lem. 11,

We can follow the same reasoning to upper bound the sum of constraints. Since the KLs are upper-bounded by $2B^{2}L^{2}/\sigma^{2}$,

Let $\bar{\omega}_{t,k}:=\frac{1}{p_{k}}\sum_{t\in\mathcal{T}_{k}^{E}}\omega_{t}$ be the average policy played in phase $k$. Since $f$ is linear and $g$ is concave, $\sum_{t\in\mathcal{T}_{k}^{E}}\left(f(\omega_{t})+\lambda g(\omega_{t},z_{k})\right)\leq p_{k}f(\bar{\omega}_{t,k})+\lambda p_{k}g(\bar{\omega}_{t,k},z_{k})$. We now set

Combining this with (G.3.5), we obtain the following inequality:

Recall that, by definition, $S_{n}=\sum_{k=0}^{K_{n}}p_{k}$. Furthermore, by Cauchy-Schwartz inequality, $\sum_{k=0}^{K_{n}}\sqrt{p_{k}}\leq\sqrt{K_{n}\sum_{k=0}^{K_{n}}p_{k}}$. Simplifying this a little,

We choose the exponential schedule $z_{k}=z_{0}e^{k}$ and $p_{k}=z_{k}e^{rk}$, where $r$ will be specified later. The left-hand side of (50) is

For $r>1$, the resulting inequality yields $K_{n}\leq\mathcal{O}(\frac{1}{r}\log\beta_{n-1})$, i.e., $K_{n}\leq\mathcal{O}(\frac{1}{r}\log\log n)$ by definition of $\beta_{n-1}$. Let us recall (G.3.4):

where we used that, from the definition of $\underline{k}$ and $z_{k}$, it must be that $k<\log(2\underline{z}(\theta^{\star})/z_{0})$. Thus,

The total number of exploration rounds is

We consider two cases, based on which of the inner terms is the maximum. In the first case, we need to bound

Since $K_{n}\leq\mathcal{O}(\frac{1}{r}\log\log n)$, this term is $\mathcal{O}((\log n)^{\frac{r-1/2}{r}})$. If the other term is the maximum, then the same procedure yields a $\mathcal{O}((\log n)^{\frac{r-1}{r}})$ dependency. Thus,