An Information-Theoretic Analysis of Thompson Sampling for Logistic Bandits

Authors: Amaury Gouverneur, Borja Rodríguez Gálvez, Tobias Oechtering, Mikael Skoglund
Primary area: learning theory
Keywords: multi-armed bandits, logistic bandits, information-theory, Thompson Sampling, regret bounds, online optimization

Abstract:
We study the performance of the Thompson Sampling algorithm for logistic bandit problems, where the agent receives binary rewards with probabilities determined by a logistic function, $\exp(\beta \langle a, \theta \rangle)/(1+\exp(\beta \langle a, \theta \rangle))$, with slope parameter $\beta$. We focus on the setting where both the action $a$ and parameter $\theta$ lie within the $d$-dimensional unit ball. Adopting the information-theoretic framework introduced by (Russo & Van Roy, 2015), we analyze the information ratio, a statistic that quantifies the trade-off between the information gained about the optimal action and the immediate regret incurred.
We improve upon previous results by establishing that the information ratio is bounded by $\tfrac{9}{2}d\alpha^{-2}$, where $\alpha$ is a minimax measure of the alignment between the action space and the parameter space, independent of $\beta$. Notably, we derive a regret bound of order $O(d/\alpha\sqrt{T \log(\beta T/d)})$, which scales only logarithmically with the logistic function parameter $\smash{\beta}$. To the best of our knowledge, this is the first regret bound for logistic bandits that achieves logarithmic dependence on $\beta$ while being independent of the number of actions. In particular, when the action space encompasses the parameter space, 
the expected regret of Thompson Sampling is of order $\tilde{O}(d \sqrt{T})$.

Decision: reject
Reviewer scores: 5, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730585703047

thread_type:
official_review

<thread_object>
creator: reviewer_qhu8

<content>
summary:
The authors derive regret bounds for Thompson sampling applied to a logistic bandit setting. In particular, the authors use the information-ratio technique (Russo & Van Roy) to first upper bound the information ratio, and use that to obtain the regret bound. Crucially, the regret bound is only logarithmically dependent on the "logistic function parameter". Furthermore, though the general regret bound the authors propose has a 1/\alpha term, \alpha being the minmax alignment constant, and this is impossible to remove (as observed in Dong & Van Roy), the authors look at special cases where the dependency can indeed be removed, leading to sub-linear regret bound \tilde{O}(d\sqrt{T}).

strengths:
The main strength of the paper is that it resolves previous gaps in the theory for Thompson sampling applied to logistic bandits. Specifically, this is the first work that has a log dependency on the logistic function parameter, when the number of actions can be large. The authors also show that in the case when the action spaces encompasses the parameter space, the expected regret of Thompson sampling does not depend on the min-max alignment constant, which was previously known to be an obstacle in obtaining good regret bounds.

weaknesses:
I don't have any particular weaknesses in mind, except the compatibility of the paper to the conference. It would also be nice for the authors to talk about some practical implications.

questions:
Can the results be extended to information directed sampling?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730681302520

thread_type:
official_review

<thread_object>
creator: reviewer_sdhq

<content>
summary:
The paper analyses the Thompson Sampling (TS) algorithm applied to logistic bandit problems, where an agent selects actions based on binary rewards determined by a logistic function. The author defines the minimax alignment constant $\alpha:= \min_{\theta \in \mathcal{O}} \max_{a\in \mathcal{A}} <a, \theta>$ to be included in the regret upper bound (also appears in Dong et al., 2019 as the \textit{ worst-case optimal log odds}) where $\mathcal{O}$ is the parameter space and $\mathcal{A}$ is the action space. The final regret bound is $O(d/\alpha \cdot T^{1/2})$ ignoring the logarithmic factor, where $d$ is the dimension of the parameter space and $T$ is the time horizon. The author improves the regret bound shown in Dong et al., which is believed to be the most relevant proceeding work, by dropping the fragility dimension $\eta$. Since $\eta$ could go exponentially with dimension $d$, dropping the dependency on $\eta$ can tighten the regret upper bound.
The regret bound present in this work is also believed to be the first regret bound for logistic bandits that achieve $\log(\beta)$ dependency.

strengths:
The paper is well-written with clear explanations and well-structured arguments that enhance the accessibility of complex ideas. The upper bound of regret is tighter than the most advanced result in the literature. The proof stream is clear to the reader.

weaknesses:
In comparing results from multiple works (table 1), Dong et al. have not been included, while it should be an important preceding since some major concepts are borrowed from there, such as the minimax alignment constant. Essentially, the work should emphasize the improvement of Dong et al.

Also, the details of the Thompson Sampling algorithm could be elaborated more, such as how the posterior sampling distribution has been established and how the parameters have been updated once the agent collects a new reward.

questions:
Please refer to the weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730719587776

thread_type:
official_review

<thread_object>
creator: reviewer_mvqr

<content>
summary:
The paper studies the performance of Thompson sampling for logistic bandit problems and improves upon previous results.

strengths:
Using the information theoretic framework of (Russo & Van Roy, 2015), this paper improves upon the previous regret bounds for Thompson sampling in logistic bandit problems. In particular, it removes dependence on the "fragility dimension" which is known to grow exponentially in some cases.

weaknesses:
1. In Lines 77 to 83, it is claimed that the main result of (Dong et al, 2019) is incorrect. This is a strong claim that requires an equally strong proof.  
First, it is claimed that they do not provide a rigorous proof for generalizing their bound to larger values of $\beta$.
However, there is no discussion about the specifics of this proof or why it might not be rigorous.     
Second, it is claimed that their regret analysis relies on the rate-distortion bound in (Dong & Van Roy, 2018) which specifically requires a bound on the "one-step compressed Thompson sampling information ratio".
However, the result of (Dong & Van Roy, 2018) that is used in (Dong et al, 2019) is stated in the form of Proposition 9 in (Dong et al, 2019) and does not require such bounds.
It is true that this result, as it is written does not appear in (Dong & Van Roy, 2018).
Proposition 9 in (Dong et al, 2019) is based on Theorem 4 in (Dong & Van Roy, 2018) which uses the notion of one-step compressed information ratio.
However, when the (normal notion of) information ratio is bounded, then the result seems to be simpler to prove.
In fact, looking at the proof of Theorem 4 in (Dong & Van Roy, 2018), it seems that the the notion of one-step compressed information ratio only appears through Conjecture 1 and if we instead have a uniform bound on information ratio, then we could directly use Proposition 1 instead of Theorem 1 and obtain the result stated in (Dong et al, 2019).  
If my understanding is correct, then the mistake in (Dong et al, 2019) is that they didn't include an argument in the spirit of what I described, but their result holds.

2. Proposition 11 in (Dong et al, 2019) states that no regret bound of the form $f(\alpha)p(d)T^{1 - \epsilon}$ is possible.
This does not imply that removing dependence on alpha is not possible.
A claim that is mentioned both in the paragraph from lines 292 to 298 and in the conclusion section.
Instead, what it implies is that removing dependence on both beta and eta *at the same time* (without introducing other problem-dependent terms) is not possible.
The regret bound of (Dong et al, 2019), specifically in their Theorem 5, removes dependence on beta, but depends on eta. (which in some cases may grow exponentially)
Your regret bound, in Theorem 2, removes dependence on eta, but depends on beta.

3. In the case A = O, Corollary 2 seems to be a weaker version of Theorem 1 in (Dong et al, 2019).
A sentence should be added next to the Corollary to discuss how it compares to that theorem.

questions:
Why can we assume that the mapping $\pi_*$ is one-to-one?
This is mentioned in the footnote of page 3, but this argument seems to be about settings where we could duplicate actions.
Is this trivial that we could do that in the logistic bandit setting?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730993119629

thread_type:
official_review

<thread_object>
creator: reviewer_goke

<content>
summary:
This paper investigates Thompson Sampling (TS) in the context of logistic bandit problems, where rewards are binary and determined by a logistic function. The authors analyze the information ratio to provide a refined regret bound that scales logarithmically with the slope parameter of the logistic function, $\beta$, independent of the number of actions. This approach purportedly improves upon prior bounds that exhibit exponential dependency on $\beta$. Additionally, the paper presents conditions under which dependence on certain alignment constants can be reduced, along with theoretical regret bounds based on this framework.

strengths:
1: The paper offers a refined theoretical analysis for Thompson Sampling in logistic bandits, claiming improved regret bounds that scale logarithmically with $\beta$.

2: The use of information-theoretic concepts, particularly the information ratio, is well-aligned with recent trends in bandit research and has the potential to contribute to a deeper understanding of the regret of logistic bandits.

weaknesses:
1. Lack of technical novelty: while the paper presents a refined analysis, the techniques used are predominantly based on established methods. The information-theoretic approach and analysis of TS have been well-studied in prior work. The paper could benefit from highlighting the unique challenges or technical hurdles in applying these methods to logistic bandits, which are not sufficiently emphasized.

2. Narrow scope: The scope of the study is somewhat limited to logistic bandits without any exploration into a broader class, such as generalized linear models. 

3. The paper does not introduce any new algorithms or propose an experimental validation to support its theoretical claims. 

4. Bayesian Regret Bounds: The preference for Bayesian regret bounds over frequentist bounds may not appeal to other audiences.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732909666305

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Comment to all reviewers

comment:
We sincerely thank the reviewers for their valuable and constructive feedback. In response to the discussion, we have added three new and insightful appendix sections to the paper:
- *Appendix D* illustrates the improvement of our regret analysis over previous works through numerical experiments on a synthetic logistic bandit problem.  Our bound remains competitive across all values of $\beta$, outperforming (Russo & Van Roy, 2014, Proposition 4) overall and (Dong & Van Roy, 2018, Theorem 3) for $\beta \geq 2$. Importantly, we observe that both (Russo & Van Roy, 2014, Proposition 4) and (Dong & Van Roy, 2018, Theorem 3) increase exponentially with $\beta$, whereas our bound grows only logarithmically. This section also provides details regarding the update of the Thompson Sampling posterior for logistic bandits.
- In *Appendix E*, we elaborate on the gaps in (Dong et al., 2019) and explain how these gaps invalidate their regret analysis. We provide both high- and low-level analyses to clearly identify which part of the proof in (Dong et al., 2019) fails and why.
- Lastly, *Appendix F* rigorously explains the construction of $\pi_\star$ to ensure it is a one-to-one mapping.

We sincerely appreciate the detailed feedback, which has helped us improve our work through additional clarifications. If our responses have adequately addressed your concerns, we hope you will consider re-evaluating your score. Should there be any remaining issues, we would be happy to provide further details.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper investigates Thompson Sampling (TS) in the context of logistic bandit problems, where rewards are binary and determined by a logistic function. The authors analyze the information ratio to derive a refined regret bound that scales logarithmically with the slope parameter of the logistic function, offering an improvement over previous results from Dong & Van Roy (2018) and Dong et al. (2019).

While the reviewers acknowledged the improvement in regret bounds, they also noted significant limitations in the paper. These include a lack of technical novelty, limited empirical evaluation, and narrow applicability restricted to logistic bandits, without extending to broader bandit classes. Additionally, the paper misses an important reference: Kveton et al. (2020), Randomized Exploration in Generalized Linear Bandits. This work provides strong frequentist regret guarantees for generalized linear bandits using Thompson Sampling, a setting that subsumes the logistic bandit problem studied in this paper.

Given the lack of novel techniques, the limited scope of the work, and the omission of a critical related paper, I recommend rejection in its current form. I encourage the authors to carefully elaborate on how their results compare with the frequentist regret analysis of Thompson Sampling for generalized linear bandits, which is known to be both more general and more challenging than the setting addressed here.