Thompson Sampling for Multi-Objective Linear Contextual Bandit

We thank the reviewer for your time and thoughtful review of our paper. We greatly appreciate the insightful feedback, especially the positive recognition of our use of optimistic sampling.

Computational Cost : We will gladly discuss the computational complexity of our proposed approach. Unlike previous works that require computing the entire Pareto front, which involves comparing all pairs of arms and has a computational complexity of $O(K^2)$ (where $K$ is the number of arms), our method significantly reduces the computational cost. Instead of explicitly identifying all effective Pareto optimal arms, we play an arm based on a random weight vector, thus selecting an arm that is optimal with respect to the random weight, which is effective Pareto optimal arm. This approach takes the computational complexity to $O(KL)$. Our method saves computational time since $K>>L$.

Discussing the computational complexity involves several factors, including both the selection of arms and the method for computing the Pareto front. Beside comparing computational complexity between UCB and TS which involves considering multiple factors of each algorithm, our experiments show that the proposed Thompson Sampling algorithm is computationally faster. We believe that the computational efficiency of TS, as demonstrated empirically, arises from the way it avoids the explicit computation of the entire Pareto front and instead samples arms based on a random weight vector, leading to lower computational overhead. The following table shows the average time complexity with $T = 10000$, and $L = 4$.

It is also important to mention that anthor main reason of using TS over UCB is the superior empirical regret performances which are presented in the experiments in the paper (Figure 2~13).

The constant dependency with respect to $M$ : The regret bound in Theorem 2 depends on $M$ through the term $\sqrt{2d\log\frac{2LMdT}{\delta}}$, which arises from the fact that multiple sampled parameters need to satisfy the concentration property [1]. Doubling $M$ results in a logarithmic increase only in the regret bound.

[1]Abeille and Lazaric. "Linear thompson sampling revisited" (2017).

We thank the reviewer for your time reviewing our paper. We sincerely hope that our answers can help clarify your questions.

The appendix has been uploaded. We would like to respectfully clarify that the full appendix, containing all proofs, experimental details, and additional experimental results, has been submitted as part of the supplementary material. Every theoretical claim made in the main paper is rigorously proved in the appendix, and our empirical evaluations are documented in detail.

We sincerely hope that, in light of this information, the reviewer might reconsider any concerns based on the (unintended) mistaken assumption that proofs or technical details are missing. We are concerned that an evaluation influenced by this misunderstanding could inadvertently affect the overall assessment of the well-prepared paper. We greatly appreciate the reviewer’s time and thoughtful engagement, and we are happy to point to any specific section of the appendix upon request.

We provide answers to your questions below:

Does the optimistic TS using $M$ samples behaves like UCB-type algorithm? : No, they are fundamentally different. UCB algorithm is deterministic, as they use upper confidence bound to evaluate arms, and the optimism comes from deterministically evaluating arms within the estimated confidence bounds. This algorithm is a fixed strategy for exploration.

Thompson Sampling is a randomized algorithm. The optimism in TS is handled through multiple sampling from the posterior distribution where the number $M$ controls the randomness of optimism and controls the boundary that the sampled parameters following concentration property [1] (more specifically, for every $m\in [M]$, $\lVert\tilde\theta_{t,m}^{(\ell)}-\hat\theta_t^{(\ell)}\rVert_{V_t} \le O(d\log LM)$ holds with probability at least $1-\delta$) . Even with large $M$, the maximum of the sampled parameters does not guarantee an optimistic value in the same way as UCB does.

[1] Abeille and Lazaric. "Linear thompson sampling revisited" (2017).

Comparison between greedy and UCB algorithm : We are more than happy to clarify this question. The single-metric regret measure may not fully explain the observed behavior in Figure 2 (also Figure 3~13 in Appendix F) because it is difficult to calculate a single value of regret that captures the full complexity of the reward vector across multiple objectives. It becomes more difficult as the number of objectives grows, which may lead to misleading interpretations in certain cases. To the best of our knowledge, for the first time, our paper demonstrates the experiments of objective-wise total rewards.

Pareto regret focuses on the trade-offs between objectives, but it does not account for the total rewards across all objectives. Our newly defined effective Pareto regret covers this problem, which offers a more comprehensive measure of performance. This new definition represents an important step forward in overcoming the difficulties associated with measuring the regret in multi-objective settings.

Explicit regret equation : In the Appendix B.2, Theorem 2 shows that algorithm $`MOL-TS`$ has the worst-case regret upper bound by $\left(1+\frac{2}{p-\frac{\delta}{T}}\right)c_T(\delta)\sqrt{2Td\log\left(1+\frac{T}{\lambda}\right)} + 2\delta \Delta_{\text{max}}$, where $c_T(\delta) = \left(R\sqrt{d\log\left(\frac{1+(T-1)/(\lambda d)}{\delta/L}\right)}+\lambda^{1/2}\right)\left(1+\sqrt{2d\log\frac{2LMdT}{\delta}}\right).$ The regret depends on the number $L$ and $M$ up to logarithmic factor, and it does not depend on the number of arms $K$.

Comparisons with LinTS-type algorithms for single objective : We are happy to elaborate on this. First of all, the well-known minimax lower bound for the linear contextual bandit is $\Omega(d\sqrt{T})$ [2], so there is a $\sqrt d$ gap between ours and the lower bound. (Please note that $O(\sqrt{dT})$ bounds such as Chu et al. 2011 possess $log K$ factors for finite arms and $O(d^{3/2}\sqrt T)$ regret algorithms including ours do not depend on the number of arms. We hope that we are discussing the results based on the relevant context.) The regret bound in our paper is $\widetilde O(d^{3/2}\sqrt T)$, which matches the best-known regret bound of the linear Thompson Sampling (LinTS) type algorithms (e.g., [1]) in single objective setting. It is known that this bound cannot be improved for LinTS and its variants due to the inevitable requirement of posterior variance inflation by a factor of $\sqrt d$, a limitation that arises in the analysis of worst-case regret for Thompson Sampling compared to fixed optimism-based algorithms [3]. Our work extends this well-known result to the multi-objective setting, and the core regret bound still aligns with the fundamental limitations of LinTS in single objective setting.

Our work extends this well-known result from single objective to multi-objective setting, where we also face the same fundamental limitations in terms of the scaling with $\sqrt d$. Therefore, while the regret bound in the multi-objective setting grows more complex due to the additional factor of $L$ (the number of objectives), the worst-case regret bound is $\widetilde O(d^{3/2}\sqrt T)$.

[2] Dani, Hayes, and Kakade. "Stochastic Linear Optimization under Bandit Feedback" COLT (2008).
[3] Hamidi and Bayati. "On Frequentist Regret of Linear Thompson Sampling" (2020).

What is $\delta$? : In Algorithm 1, the input $\delta$ represents a confidence bound input that plays two key roles, RLS estimations and concentration property. As described in Appendix C, $\delta$ measures the probability bound on the distance between the true parameter and the RLS estimates [4]. This ensures that the estimated parameters are close enough to true values with probability at least $1-\delta$. Also, it controls the probability that the sampled parameters follow the concentration property [1]. This property ensures that sampled parameters are close enough to RLS estimate with high probability. It is crucial property for random exploration in the Thompson Sampling algorithm, as it helps balance the trade-off between exploration and exploitation, while maintaining reliable confidence bounds.

[4] Abbasi-Yadkori et al. "Improved algorithms for linear stochastic bandits" (2011).

Extra experiments of $\lambda$, $c$, $\delta$ : The main focus of our experiments is to compare the performance of the algorithms with different values of $M$ and $L$. The other hyperparameters, including $\lambda, c$, and $\delta$ were kept fixed in our experiments, with the value set to $\lambda=1, c=1$, and $\delta=0.01$. We did explore additional results for different initial values of these hyperparameters. But these values were not central to the core ideas of our paper, and varying these parameters does not change the results. Regarding the comparison with greedy and UCB algorithm, we used the same fixed hyperparameters for fairness, ensuring that the comparison is made under consistent restriction. The following table measures the average of total regret over 10 different instances in $T = 10000$ with different $\lambda, c$, and $\delta$.

Adversarial setting : We are happy to modify Section 3 of the paper, that the contexts are adversarially given.

Thank you for the response. Most of the questions were answered by the authors. I went through the appendix and my concerns regarding this are satisfied. The paper is pretty good in terms of the theoretical contributions and I raised my score to reflect that. For the final version, it might be good to state delta used in Algorithm 1 in the main text, at least a brief note on what this parameter indicates.

While I understand that TS and UCB are fundamentally different, I meant that in this case they can be seen connected in the following way. For linUCB type methods, $\text{UCB}_t(x) = x^\top \hat{\theta}_t + \alpha \cdot \sqrt{x^\top V_t^{-1} x}$. In your case, you take $M$ samples from the posterior and take the maximum - if you look at the distribution of this, this is centered around a term roughly similar to the UCB-type, where $M$ controls the exploration-exploitation trade-off ($\alpha$). If you take one sample, then you cannot control this - taking a correct choice of $M$ properly balances this trade-off, as you show.

I am still a bit confused about Figure 2 - I understand that it is harder to metrize performance across all objectives by a single measure, but it seems greedy outperforms the MOL-UCB for ALL objectives, however, the pareto regret shows a different story. So with this new metric, it seems it is possible to do better overall (in the new metric sense) when individually you perform worse for all underlying objectives. Can the authors provide an explanation for this?

We sincerely thank the reviewer for taking the time to carefully review our paper. We especially appreciate the positive comments on the strength of our work, especially acknowledging optimistic sampling.

Regret bound of $\widetilde{O}\bigl(d^{3/2}\sqrt{T}\bigr)$ and possible adaptation of Feel-Good TS

We are happy to answer this. First, the regret bound of $\widetilde{O}\bigl(d^{3/2}\sqrt{T}\bigr)$ for our algorithm—viewed as a member of the LinTS family—is not improvable in terms of the $d$ dependence. Hamidi & Bayati (2023) [1] show that Linear Thompson Sampling incurs an inherent posterior-variance inflation by a factor of $\sqrt{d}$, leading to a frequentist regret lower bound of $\widetilde{O}(d^{3/2}\sqrt{T})$ is the best possible for LinTS-type algorithms. If not for such an inflation, LinTS-type algorithms would incur a linear regret in $T$ [1]

Our work extends this single-objective result to the multi-objective setting, and the bound we obtain remains consistent with these fundamental limitations of LinTS.

[1] Hamidi & Bayati. “On Frequentist Regret of Linear Thompson Sampling” (2023).

Adapting Feel-Good TS is indeed intriguing. However, even in the single-objective case, adding the Feel-Good exploration term typically requires approximate MCMC to sample from a non-conjugate posterior—unless strong distributional assumptions are imposed. Because we assume only classical sub-Gaussian noise, such sampling would introduce significant computational overhead.

For these reasons we base our algorithm on LinTS techniques. Extending Feel-Good TS to the multi-objective setting is an interesting avenue for future research, but lies beyond the scope of the present work.

Previous methods and our new notion of Pareto optimality: We are happy to revise the discussion to clarify how our newly defined concept—effective Pareto optimality—can benefit existing algorithms as well. Existing multi-objective bandit methods typically sample directly from the standard Pareto front, which can lead to inferior cumulative rewards across objectives. Replacing that step with our notion of effective Pareto optimality could improve the performance of those algorithms as well as our own, further underscoring the contribution of this work.

We would like to sincerely thank the reviewer for taking the time to review our paper. We address the feedback you provided point by point below.

Why linear assumption? : We appreciate the reviewer’s feedback regarding the assumption of a linear reward function, but we believe this is not a fundamental weakness of the paper. Analyzing Thompson Sampling in multi-objective bandits (particularly in contextual bandits including linear and generalized linear settings) has remained as an open problem, and to the best of our knowledge, for the first time, our work presents a fundamental milestone in the development of randomized algorithms with the (worst-case) Pareto regret guarantees in multi-objective linear contextual bandits.

The focus of our paper is providing the first randomized algorithm, with Pareto regret analysis and empirical validation in linear reward function. Extending our approach to the (non-linear) GLM is straightforward. Hence, our results aren't limited to linear settings. Further extension to handle more general function class is certainly an interesting direction. However, it is important to note that the optimistic sampling that we propose for Pareto regret analysis can be naturally generalized to other non-linear reward functions. Our work is a noteworthy contribution that sets the foundation for future work with more complex settings. Overall, the fact that we have solved this long-standing open problem in the multi-objective linear contextual bandit should be considered a notable contribution, rather than considered as a weakness.

What is a best single arm? : In multi-objective bandits—and, more broadly, in multi-objective optimization—a single best optimal solution is generally not guaranteed to exist. As noted in our Introduction, multiple objectives often conflict, so improvement in one objective can degrade another. The appropriate notion of optimality is therefore Pareto optimality: the set of solutions that cannot be improved in any objective without worsening at least one other.

If a unique “best” arm did exist under some scalarized criterion, the problem would degenerate to a single-objective bandit setting—contradicting the essence of multi-objective learning. Prior work thus focuses on identifying the Pareto-optimal set (the Pareto front), where each arm is non-dominated by the rest. However, simply enumerating Pareto arms does not address how to maximize cumulative reward across all objectives. Our contribution is to introduce effective Pareto-optimal arms, together with an algorithm that attains sub-linear regret for this richer goal. This adds a fresh perspective to the multi-objective bandit literature.

Should one wish to impose problem(or user)-specified weights and reduce the problem to a single scalar objective, our algorithm naturally specializes to that case and still guarantees sub-linear regret. Nevertheless, that scenario is not the focus of this paper, and therefore it should not be viewed as a weakness of our work.

Technical challenges in analysis : We are happy to elaborate on this. First of all, a simple, straightforward combination of Thompson Sampling (TS) techniques with existing analyses for multi-objective linear contextual bandits is not sufficient for multi-objective linear contextual bandits This gap explains why no worst-case regret analysis of TS currently exists for this setting.

As explained in Section 5.3, one of the key technical challenges in deriving the regret bound of Thompson Sampling algorithm for multi-objective linear contextual bandits lies in ensuring the probability of optimism. Previously, there are many papers of multi-objective UCB-type algorithm with Pareto regret analysis (Drugan & Nowe (2013), Tekin & Turgay (2018), Turgay et al. (2018), Lu et al. (2019), Xu & Klabjan (2023)). The analysis of UCB algorithm is almost similar to that of single objective setting, attaining Pareto regret bound $\widetilde O(d\sqrt{T})$ where the number of objectives depend up to logarithmic factor. By contrast, deriving comparable guarantees for TS in the multi-objective linear contextual setting remains an open problem, and our work is the first to tackle these technical obstacles directly.

Suppose we follow standard Thompson Sampling algorithm, by setting $M=1$. Widely known in single objective setting $(L=1)$, the probability that $\tilde\theta_t^{(1)}$ is sufficiently optimistic is $\mathbb{P}\bigl( x_{t,a_t}^\top(\tilde\theta_t^{(1)}-\hat\theta_t^{(1)})\ge c_{1,t}(\delta)\lVert x_{t,a_t}\rVert_{V_t^{-1}} \bigr) \ge \tilde p$, where $\tilde p$ is a constant probability. In multi-objective setting $(L>1)$, as the arm is randomly selected, this optimism must hold for all objectives. For any randomly selected arm, we need to ensure this optimism for all parameters $(\tilde{\theta}\_t^{(\ell)})\_{\ell\in[L]}$, i.e., $\bigcap_{\ell\in[L]}\mathbb{P}(x_{t,a_t}^\top(\tilde\theta_t^{(\ell)}-\hat\theta_t^{(\ell)})\ge c_{1,t}(\delta)\lVert x_{t,a_t}\rVert_{V_t^{-1}})\ge \tilde p^{L}$. In the worst-case, this results in the regret bound $\displaystyle\widetilde O(\frac{1}{\tilde p^L}d^{3/2}\sqrt{T})$, which become exponentially large as the number of objectives $L$ increases.

The optimistic sampling resolves this problem with multiple sampled parameters. Suppose $M>1$. For each objective $\ell\in[L]$, there are $M$ sampled parameters $(\tilde\theta\_{t,m}^{(\ell)})\_{m\in[M]}$. The arm is evaluated with the sampled parameter that maximizes the evaluation, i.e., $\tilde\theta\_{t,a}^{(\ell)}=\arg\max\_{\theta}\{(x_{t,a}^\top\tilde\theta\_{t,m}^{(\ell)})\_{m\in[M]}\}$. Then, the probability bounds for optimism become $\mathbb{P}(x_{t,a_t}^\top(\tilde\theta_{t,a}^{(\ell)}-\hat\theta_t^{(\ell)})\ge c_{1,t}(\delta)\lVert x_{t,a_t}\rVert\_{V_t^{-1}}) \ge 1-(1-\tilde p)^M$. Following above steps, we have the probability of optimism at least $(1-(1-\tilde p)^M)^L$. We choose large enough $M$ so that this probability is bounded below by $\tilde p$.

We modify Thompson sampling algorithm with optimistic sampling to ensure the optimism and attaining the regret bound $\widetilde O(d^{3/2}\sqrt{T})$. Addressing this challenging problem requires the development of a novel approach and perpectives. We would be more than happy to include more explanations in Section 5.3 in the final version to further strengthen our contributions.

Overall remarks : We appreciate the reviewer’s feedback, but we do not believe the points raised constitute fundamental weaknesses of our paper. We are confident that our work makes substantial contributions to the multi-objective contextual bandit literature and respectfully ask the reviewer to re-evaluate our work in light of our clarifications.

If any questions remain, please let us know, and we would be more than happy to provide further explanations.

We thank the reviewer for taking the time to review our paper. We sincerely appreciate the insightful comments, particularly the recognition of the optimistic sampling. We view this as an excellent opportunity to further clarify and strengthen our contributions, ensuring a more thorough understanding of our approach and its implications.

Streching Analysis on the number $L$ : We thank the reviewer for highlighting this issue. We will gladly revise the technical lemmas in Appendix C to provide a more detailed explanation of how the number of objectives $L$ affects the regret analysis of our algorithm.

The Comparison between $M=1$ and $M=\log L$, for $L=8$ : We are also grateful for this feedback and happy to show our results. Due to the limited space (by large number of objectives), we omitted the comparison between $M=1$ and $M=\log L$. We will add the results of additional experiments comparing these two settings. However, when $L\ge8$, the results demonstrate that Thompson Sampling with optimistic sampling clearly exhibits lower effective Pareto regret. The following table is the experimental results of total regret when $L=8, 12$ and $T=10000$.

The difference with respect to $d$ : As the dimension $d$ increases, the theoretical worst-case regret increases as well, due to the higher uncertainty in the parameter estimation. Empirically, this behavior is consistent with our experiments, as the regret gap between $M=1$ and $M=\log L$ grows more significant.

Why $M=1$ does not seem to be bad? : The worst-case theoretical regret bound does not imply that the algorithm must fail to the worst-case empirical results. It is essential to note that without optimistic sampling, the theoretical worst-case regret could grow exponentially. We resolve this issue by adopting optimistic sampling in $`MOL-TS`$, which mitigate the potential for exponential growth in regret. However, the empirical results do not necessarily be the worst-case scenario. While optimistic sampling still achieving better outcomes empirically, optimistic sampling is employed in $`MOL-TS`$ to resolve the theoretical issue and ensure better performance in the worst-case scenario.