An Information-Theoretic Analysis of Thompson Sampling for Logistic Bandits

Venue: NeurIPS_cc_2024_Workshop_BDU
Published: 2024-08-30 10:33:49

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))$. We focus on the setting where the action $a$ and parameter $\theta$ lie within the $d$-dimensional unit ball with the action space encompassing the parameter space. Adopting the information-theoretic framework introduced by Russo and Van Roy (2015), we analyze the information ratio, which is defined as the ratio of the expected squared difference between the optimal and actual rewards to the mutual information between the optimal action and the reward. Improving upon previous results, we establish that the information ratio is bounded by $\tfrac{9}{2}d$. Notably, we obtain a regret bound in $O(d\sqrt{T \log(\beta T/d)})$ that depends only logarithmically on the parameter $\beta$.

Main paper: 
 problem setup: 
 We consider a logistic bandit problem, where at each time step t ∈ {1, . . . , T }, an agent selects an action A t and receives a binary reward R t ∈ {0, 1} with probability following a logistic function:P(R t = 1|A t = a, Θ = θ) =exp(β⟨a, θ⟩) 1 + exp (β⟨a, θ⟩) .Here, β is a known scale parameter, and ⟨a, θ⟩ denotes the inner product of the action vector a ∈ A and the unknown parameter θ ∈ O. The logistic function, sometimes referred to as the link function, is denoted ϕ β (⟨a, θ⟩). In this setting, the action a lies within the d-dimensional Euclidean unit ball, B d (0, 1), and the parameter vector θ on the d-dimensional Euclidean unit sphere, S d (0, 1).Additionally, we assume the action space A encompasses the parameter space O, that is O ⊆ A. Note that this ensures that, for each θ ∈ O, there exist an action a ∈ A equal to θ, such that ⟨a, θ⟩ = 1.Following the Bayesian framework, we assume the parameter vector θ is sampled from a known prior distribution P Θ . As the reward distribution depends only on the selected action and the parameter, it can be written as R t = R(A t , Θ). The agent's history at time t is denoted byH t = {A 1 , R 1 , . . . , A t-1 , R t-1 }, representing all past actions and rewards observed up to time t.The goal of the agent is to sequentially select actions that maximize the total accumulated reward, or equivalently, that minimize the total expected regret defined as:E[Regret(T )] := E T t=1 R(A ⋆ , Θ) -R(A t , Θ) ,where A ⋆ is the optimal action for the parameter Θ. We construct the optimal mapping π ⋆ (θ) :=argmax a∈A E[R(a, θ)] and define A ⋆ = π ⋆ (Θ).The expectation is taken over the randomness of the action selection, the reward distribution, and the prior distribution of the parameter Θ.Since the σ-algebras of the history are often used in conditioning, we introduce the notations Take the corresponding optimal action A t = π ⋆ ( Θt ).E t [•] := E[Collect the reward R t = R(A t , Θ).Update the historyH t+1 = H t ∪ {A t , R t }. 7: end forStudying the regret of TS in bandit problems, Russo and Van Roy (2015) introduced a key quantity to the analysis, the information ratio defined as the following random variable:Γ t := E t [R(A ⋆ , Θ) -R(A t , Θ)] 2 I t (A ⋆ ; R(A t , Θ), A t ) .This ratio measures the trade-off between minimizing the current squared regret and gathering information about the optimal action. Russo and Van Roy use this concept to provide a general regret bound that depends on the time horizon T , the entropy of the prior distribution of A ⋆ , and an algorithm-and problem-dependent upper bound Γ on the average expected information ratio (Russo and Van Roy, 2015, Proposition 1) .A limitation of this approach is that the prior entropy of the optimal action, H(A ⋆ ), can grow arbitrarily large with the number of actions or get infinite if the action space is continuous. We address this issue with Theorem 1, where we propose a regret bound that depends instead on the entropy of Θ ε , a quantized version of the parameter Θ. The quantized parameter, defined in Definition 1, is obtained by setting Θ ε as the closest approximation for Θ on an ε-net for the metric space (O, ρ).Definition 1 Let the set O ε be an ε-net for (O, ρ) with associated projection mapping q : O → O ε such that for all θ ∈ O we have ρ(θ, q(θ)) ≤ ε. We define the quantized parameter as Θ ε := q(Θ). 
main results: 
 This section presents our main results on the regret of TS for logistic bandits. In Theorem 1, we start by leveraging the previously introduced concepts to derive an information-theoretic regret bound that holds for continuous and infinite parameter spaces. Following this, we state in Proposition 1 our principal contribution, where we prove a bound of 9 2 d on the TS information ratio. Combining this result with our regret bound, we derive in Theorem 2, a bound on the expected regret of TS for logistic bandits, which scales as O(d T log(βT /d)).The first theorem we present is an adaptation of (Gouverneur et al., 2023, Theorem 2) and (Neu et al., 2021, Theorem 2) to the logistic bandits setting. It relates the regret of TS to the entropy of the quantized parameter Θ ε .Theorem 1 Under the logistic bandit setting with logistic function ϕ β (x) = e βx /(1 + e βx ), let Θ ε be defined as in Definition 1 for some ε > 0. Assume that the average expected TS information ratio is bounded,1 T T t=1 E[Γ t ] ≤ Γ, for some Γ > 0.Then, the TS cumulative regret is bounded asE[Regret(T )] ≤ ΓT (H(Θ ε ) + εβT ).Notably, the above theorem holds for continuous action and parameter spaces and works with bounds on the average expected information ratio of the "standard" TS, instead of the one-step compressed the information ratio. We explore this difference in more detail in Appendix B.The proof of Theorem 1 relies on an approximation of the conditional mutual information I(Θ; R t |A t , H t ) as I(Θ ε ; R t |A t , H t ) + βε exploiting the fact that, for all a ∈ A and θ ∈ O, the log-likelihood of R(a, θ) is β-Lipschitz with respect to θ. The proof is presented in Appendix A.In the following proposition, we present our main contribution, a bound on the information ratio of TS that depends only on the dimension d of the problem. This result confirms, under the considered setting, and up to a multiplicative factor of 9, the conjecture of Dong and Van Roy (2018) .Proposition 1 Under the logistic bandit setting with logistic function ϕ β (x) = e βx /(1 + e βx ), let A ⊆ B d (0, 1) and O ⊆ S d (0, 1) be such that O ⊆ A. Then, for all β > 0, the TS information ratio is bounded asΓ t ≤ 9 2 d.The proof of Proposition 1 is presented in Appendix B. At a high level, our proof consists of three parts: a lower bound on the mutual information, an upper bound on the squared expected regret at time t, and an upper bound on a ratio of expected variances by the study of the limit case β → ∞. A quantity that plays a central role in our analysis is the expected variance of the reward probabilityϕ β (⟨A t , Θ⟩) conditioned on Θ, E t [V t [ϕ β (⟨A t , Θ⟩)|Θ]].It is used as a lower bound on the mutual information and a related quantity shows up in the upper bound on the squared expected regret.By combining Proposition 1 with Theorem 1, we arrive at our main result: a bound on the expected TS regret that scales as O(d T log(βT /d)).Theorem 2 Under the logistic bandit setting with logistic function ϕ β (x) = e βx /(1 + e βx ), letA ⊆ B d (0, 1) and O ⊆ S d (0, 1) be such that O ⊆ A.Then for all β > 0, the TS regret is bounded as To the best of our knowledge, this is the first regret bound for logistic bandits that scales only logarithmically with the logistic function's parameter β while remaining independent of the number of actions. We note that it is within a factor of O( log(βT /d)) of the minimax lower bound Ω(dE[Regret(T )] ≤ 3d T log 3 + 6βT d .√ T )from (Dani et al., 2008) . 
conclusion and future work: 
 In this paper, we studied the Bayesian regret of the Thompson Sampling algorithm for sequential decision-making problems under uncertainty, focusing on logistic bandit problems with action and parameter spaces in the d-dimensional unit ball. We improved the state-of-the-art bounds, proving that when the action space A encompasses the parameter space O, the information ratio of TS is bounded by 9 2 d. Using this result, we established that TS expected regret is bounded by O(d T log(βT /d)).A natural direction for future work is to extend our bounds to settings where the action space does not fully encompass the parameter space. This extension requires careful analysis of how well the action space aligns with the parameter space, a property closely related to the fragility dimension, η(A, O), introduced by Dong et al. (2019) . This quantity is crucial for the analysis of logistic bandits, as Dong et al. (2019) demonstrated that there cannot be an η(A, O)-independent upper bound that is both polynomial in d and sub-linear in T . In cases where the action space does encompass the parameter space, this fragility dimension is minimal, equal to d + 1. However, in problems where this relation is not satisfied and with dimension d ≥ 3, the fragility dimension can grow significantly and become as large as the cardinality of the action set. Future research should take this challenge into consideration to develop regret bounds applicable to more general settings. 
: 
 of the action space |A|. Dong et al. (2019) provided a bound of 100d on the information ratio for TS when β < 2. They also suggested, through numerical computations, that this bound holds for larger values of β. However, their work has two key limitations. First, they do not provide a rigorous proof for generalizing to larger β values. Second, and more critically, their regret analysis is incomplete as it relies on the rate-distortion bound from Dong and Van Roy (2018) , which specifically requires a bound on the one-step compressed TS information ratio; a fundamentally different quantity from the TS information ratio they studied. Notably, their techniques to bound the TS information ratio do not apply to the one-step compressed TS information ratio.In this work, we address these issues and propose a regret bound that scales only logarithmically with the slope of the logistic function. Our key contributions are as follows:• We propose an information-theoretic regret bound for infinite and continuous action and parameter spaces that relies on the entropy of the quantized parameter, H(Θ ε ). This result is achieved by adapting the approaches from Neu et al. (2021) and Gouverneur et al. (2023) to the logistic bandit setting.• We present a refined analysis showing that for all β > 0, the information ratio of TS for logistic bandits is bounded by 9 2 d, improving upon previous results.• We establish a bound of O(d T log(βT /d)) on the regret of TS. To our knowledge, this is the first bound on logistic bandits that scales only logarithmically on β > 0 and is independent of the number of actions. 
 
 Appendix: Theorem 1 Under the logistic bandit setting with logistic function ϕ β (x) = e βx /(1 + e βx ), let Θ ε be defined as in Definition 1 for some ε > 0. Assume that the average expected TS information ratio is bounded,1 T T t=1 E[Γ t ] ≤ Γ, for some Γ > 0.Then, the TS cumulative regret is bounded asE[Regret(T )] ≤ ΓT (H(Θ ε ) + εβT ).Proof 1 We start by rewriting the expected regret of TS using the information ratio:E[Regret(T )] = T t=1 E t [R(A ⋆ , Θ) -R(A t , Θ)] = E t Γ t I t (A ⋆ ; R(A t , Θ), A t ) .We continue using Jensen's inequality and applying Cauchy-Schwartz inequality:E[Regret(T )] ≤ T t=1 E t [Γ t ]I t (A ⋆ ; R(A t , Θ), A t |H t ) ≤ ΓT T t=1 I t (A ⋆ ; R(A t , Θ), A t |H t )where in the last inequality, we used thatT t=1 E t [Γ t ] ≤ ΓT .Applying the chain rule ( (Yury Polyanskiy, 2022, Theorem 3.7.b)) we can decompose the mutual information asI t (A ⋆ ; R(A t , Θ), A t |H t ) = I t (A ⋆ ; A t |H t ) + I t (A ⋆ ; R(A t , Θ)|H t , A t ) = I t (A ⋆ ; R(A t , Θ)|H t , A t ),where we used the fact that the mutual information I t (A ⋆ ; A t |H t ) = 0 as the optimal action A ⋆ and the TS action A t are independent conditioned on the history H t .Let f Rt|H t ,At,Θ denote the probability density of R t conditioned on H t , A t , Θ and f Rt|H t ,At denote the probability density on H t , A t . Then the mutual information terms can be written asI(Θ; R t |H t , A t ) = E log f Rt|H t ,At,Θ (R t ) f Rt|H t ,At (R t ) .We let the set O ε be an ε-net for (O, ρ) with associated projection mapping q : O → O ε such that for all θ ∈ O we have ρ(θ, q(θ)) ≤ ε. Similarly, as in the proof of (Neu et al., 2021 , Theorem 2), we note that the mutual information can equivalently be written asEQUATIONsince f Rt|H t ,At,Θ = f Rt|At,Θ a.s. by the conditional Markov chain R t -A t -H t | Θ.Since the derivative of log(ϕ β (x)) is equal to β/(1 + exp(βx)), it is bounded by β and is thereforeβ-Lipschitz.As for all a ∈ A and all θ ∈ O, the inner product ⟨a, θ⟩ ≤ 1, we conclude thatlog(f Rt|At,Θ=θ (1)) is β-Lipschitz with respect to θ. Similarly d dx log(1-ϕ β (x)) = -β exp(βx)/(1+ exp(βx)) is also bounded by β and is therefore β-Lipschitz. We get that log(f Rt|At,Θ=θ (0)) is β-Lipschitz with respect to θ. We conclude that | log f Rt|At,Θ=θ (R t ) -log f Rt|At,Θ=q(θ) (R t )| ≤ βρ(θ, q(θ)) ≤ βε.Then, defining the random variable Θ ε := q(Θ), we note that the second term in (1) is equal toI(Θ ε ; R t |H t , A t ). Summing the T mutual information I(Θ ε ; R t |H t , A t ) and applying the chain rule (see (Yury Polyanskiy, 2022, Theorem 3.7.e)), we obtainE[Regret(T )] ≤ ΓT (I(Θ ε ; H T ) + εβT ).Finally, we upper bound the mutual information I(Θ ε ; H T ) by the entropy H(Θ ε ) as in (Yury Polyanskiy, 2022, Theorem 3.4.e) to obtain the claimed result.This section presents the key ideas of the proofs of our main contribution, Proposition 1.Proposition 1 Under the logistic bandit setting with logistic function ϕ β (x) = e βx /(1 + e βx ), let A ⊆ B d (0, 1) and O ⊆ S d (0, 1) be such that O ⊆ A. Then, for all β > 0, the TS information ratio is bounded as Γ t ≤ 9 2 d.Under the logistic bandit setting with link function ϕ β , the reward R(A t , Θ) is given by a Bernoulli random variable with associated probability ϕ β (⟨A t , Θ⟩). We use the notation Bern(ϕ β (⟨A t , Θ⟩)) to make the setting more explicit. Since we assumed the action space A encompasses the parameter space O and both are subsets of a d-dimensional unit sphere, the optimal action is to select the action that aligns with the parameter, π ⋆ (θ) = θ. We can therefore writeR(A ⋆ , Θ) = R(π ⋆ (Θ), Θ)equivalently as Bern(ϕ β (⟨Θ, Θ⟩)) and similarly, write R(A t , Θ) as Bern(ϕ β (⟨ Θt , Θ⟩)). To alleviate the writing, we will omit the the subscript t notation for the rest of the section.Equipped with this new notation, we recall the definition of the information ratio:Γ(Θ, Θ)= E[Bern(ϕ β (⟨Θ, Θ⟩)) -Bern(ϕ β (⟨ Θ, Θ⟩))] 2 I(Θ; Bern(ϕ β (⟨ Θ, Θ⟩)), Θ) .Our proof can be broadly divided into three key components: establishing a lower bound on the mutual information, deriving an upper bound on the squared expected regret, and obtaining an upper bound on a ratio of expected variances by analyzing the limit case as β → ∞. A crucial element in our analysis is the expected variance of ϕ β (⟨ Θ, Θ⟩) conditioned on Θ, expressed asE[V[ϕ β (⟨ Θ, Θ⟩)|Θ]].It appears in the lower bound on mutual information and a related quantity is used to upper bound the squared expected regret.We start by giving a general lemma that relates the mutual information between a random variable U and a Bernoulli random variable with probability U to the variance of the random variable U .Lemma 1 Let U be a random variable taking values in [0, 1] and Bern(U ) be a Bernoulli random variable with probability U . Then it holds that,I(U ; Bern(U )) ≥ 2V(U ).Proof 2 The proof uses the decomposition of mutual information as a difference of entropy and the Taylor expansion of the binary entropy function. Using proposition Yury Polyanskiy (2022)[Theoremwe can decompose the mutual information between U and Bern(U ) asI(U ; Bern(U )) = h(Bern(U )) -h(Bern(U )|U ) Following Duchi (2016)[Example 2.2] notation, we define h 2 (p) := -p log(p) -(1 -p) log(1 -p)for p ∈ (0, 1). We note that we can rewrite the mutual information asI(U ; Bern(U )) = h 2 (E[U ]) -E[h 2 (U )].(2) From a Taylor expansion of h 2 (x) we have thath 2 (x) = h 2 (p) + (x -p)h ′ 2 (p) + 1 2 (x -p) 2 h ′′ 2 (ξ)for some ξ ∈ (x, p). We can compute the second derivative of h 2 (x). We get h ′′ 2 (x) = -1x(1-x)for x ∈ (0, 1). This function is concave and is maximal at x = 1/2, where it takes the value h ′′ 2 (1/2) = -4. We then have that for all x ∈ [0, 1] and all p ∈ [0, 1],h 2 (x) ≤ h 2 (p) + (x -p)h ′ 2 (p) -2(x -p) 2 . Using this fact for x = U and p = E[U ], we have that h 2 (U ) ≥ h 2 (E[U ]) + (U -E[U ])h ′ 2 (E[U ]) -2(U -E[U ]) 2 .Applying the last inequality to the second term in (2), it comes thatI(U ; Bern(U )) ≥ E h 2 (E[U ])-h 2 (E[U ])-(U -E[U ])h ′ 2 (E[U ])+2(U -E[U ]) 2 .Finally, simplifying terms and taking the expectation gives the desired result.Equipped with Lemma 1, we can now state and prove our lower bound on the mutual information I(Θ; Bern(ϕ β (⟨ Θ, Θ⟩)), Θ).Lemma 2 Let the link function be ϕ β (x) = e βx /(1 + e βx ), then, it holds thatI(Θ; Bern(ϕ β (⟨ Θ, Θ⟩)), Θ)≥ 2E V ϕ β (⟨ Θ, Θ⟩)| Θ .Proof 3 We start the proof by applying the chain rule. It comes thatI Θ; Θ, Bern ϕ β (⟨ Θ, Θ⟩) = I Θ; Θ + I Θ; Bern ϕ β (⟨ Θ, Θ⟩) | Θ (i) = I Θ; Bern ϕ β (⟨ Θ, Θ⟩) | Θ (j) = I Θ; Bern ϕ β (⟨ Θ, Θ⟩) | Θ (k) = E[I ϕ β (⟨ Θ, Θ⟩); Bern ϕ β (⟨ Θ, Θ⟩) | Θ = θ],where (i) follows as Θ and Θ are independent conditioned on the history; (j) follows as Θ and Θ are identically distributed conditioned on the history; and (k) is obtained by taking the expectation over Θ and using (Yury Polyanskiy, 2022, Theorem 3.2.d) as ϕ β (⟨θ, x⟩) is a one-to-one mapping. Finally, applying Lemma 1 yields the desired result.We note that this result would not be possible to obtain for mutual information of the "one-step compressed Thompson Sampling" as equality (j) requires Θ and Θ to be identically distributed.A quantity that will naturally come up often is the expected difference between of the parameter Θ and the sampled ones Θ and how it relates to the expected difference of rewards ϕ β (⟨Θ, Θ⟩)-ϕ β (⟨ Θ, Θ⟩).To alleviate the notations, we define ψ β (x) := ϕ β (1) -ϕ β (1 -x).Observing that ⟨Θ, Θ⟩ = ||Θ|| 2 2 = 1, we have indeedϕ β (⟨Θ, Θ⟩) -ϕ β (⟨ Θ, Θ⟩) = ϕ β (1) -ϕ β (⟨ Θ, Θ⟩) = ψ β (1 -⟨ Θ, Θ⟩).The two following lemmata from Dong and Van Roy (2018) will be of importance for our analysis.Lemma 3 ( (Dong and Van Roy, 2018, Lemma 16 )) Let U, V be random vectors in R d , and let Ũ , Ṽ be independent random variables with distributions equal to the marginals of U, V , respectively.ThenE U ⊤ V 2 ≤ d • E Ũ ⊤ Ṽ 2 .Lemma 4 ((Dong and Van Roy, 2018, Lemma 18)) Let f : R + → R + be such that f (0) ≥ 0 andf (ζ)/ζ is non-decreasing over ζ ≥ 0.Then, for any non-negative random variable U , there isE[f (U )] 2 E[U ] 2 ≤ V[f (U )] V[U ].The function ψ β (x) satisfies the first two requirements from Lemma 4: applied on the difference of inner products ⟨Θ, Θ⟩ -⟨ Θ, Θ⟩, it is a mapping from [0, 2] to [0, 1] andψ β (0) = ϕ β (1) -ϕ β (1 -0) = 0.However, it fails to satisfy the third requirement; ψ β (x)/x increases initially, reaching a maximum between 1 and 2 before decreasing (see in Remark 1). This issue leads to the introduction of a modified function, which we call the logistic surrogate, as the tightest upper bound ψ β (x) on that satisfies the last requirement from Lemma 4.Definition 2 (Logistic surrogate) We construct the logistic surrogate function φ β as the tightest upper bound on ψ β (x) such that φ β (x)/x is non-decreasing over x ≥ 0.Namely, let δ β = arg max x∈[0,2] ψ β (x)x , we define the function φ β asφ β (x) = ψ β (x) x ∈ [0, δ β ], ψ β (δ β ) + (x -δ β ) • ψ β (δ β )/δ β x ∈]δ β , 2].We are now equipped to state and prove an upper bound on the squared expected regret.Lemma 5 Let the logistic surrogate be defined as in Definition 2. Then, it holds thatE[Bern(ϕ β (⟨ Θ, Θ⟩)) -Bern(ϕ β (⟨ Θ, Θ⟩))] 2 ≤ d • E V φ β (1 -⟨ Θ, Θ⟩)| Θ .Proof 4 Integrating over the randomness of the Bernoulli outcome, we can write the squared expectedregret as E[ϕ β (⟨Θ, Θ⟩) -ϕ β (⟨ Θ, Θ⟩)] 2 = E[ψ β (1 -⟨ Θ, Θ⟩)] 2. By the definition of φ β , we haveφ β (x) ≥ ψ β (x).Using this and the law of total expectation, we have thatE[ψ β (1 -⟨ Θ, Θ⟩)] 2 ≤ E[E[φ β (1 -⟨ Θ, Θ⟩)|Θ]] 2 .We now apply Lemma 4 onE[φ β (1 -⟨ Θ, Θ⟩)|Θ]. It comes that E[E[φ β (1 -⟨ Θ, Θ⟩)|Θ]] 2 ≤ E V φ β 1 -⟨ Θ, Θ⟩ | Θ V 1 -⟨ Θ, Θ⟩ | Θ :=U (Θ) E 1 -⟨ Θ, Θ⟩ | Θ 2 = E U (Θ)⟨Θ, Θ⟩ -⟨ Θ, Θ⟩ 2 = E ⟨U (Θ)Θ, Θ -Θ⟩ 2 .Finally, we apply Lemma 3 with U = U (Θ)Θ and V = Θ -Θ and rearrange terms to obtain the claimed result:E ⟨U (Θ)Θ, Θ -Θ⟩ 2 ≤ d • E ⟨U (Θ)Θ, Θ -Θ⟩ 2 = d • E U (Θ) 2 E ⟨Θ, Θ -Θ⟩ 2 Θ = d • E   V φ β 1 -⟨ Θ, Θ⟩ | Θ V 1 -⟨ Θ, Θ⟩ | Θ V ⟨ Θ, Θ⟩ | Θ   = d • E V φ β 1 -⟨ Θ, Θ⟩ | Θ .Putting together Lemma 2 and Lemma 5, we get that the information ration Γ(Θ, Θ) can be bounded byΓ(Θ, Θ) ≤ d/2 • E V φ β 1 -⟨ Θ, Θ⟩ | Θ E V ψ β 1 -⟨ Θ, Θ⟩ | Θ .The last part of the proof, Appendix B.3, takes care of controlling the ratio of expected variances over the functions φ β and ψ β .By definition, the function ψ β and its surrogate φ β are equal for x ∈ [0, δ β ] and then diverge linearly at a rate of ψ β (δ β )/δ β . We observe, in Remark 1, that δ β is a decreasing function of β and that ψ β (δ β )/δ β strictly increases with β.This observation suggests that studying the case β → ∞ could provide a general upper bound. Indeed, taking the limit case β → ∞, the domain where the two functions differ is maximized, and the rate at which they differ is the largest. We show in Lemma 7 that under some simple transformations, increasing the value of β does lead to a larger ratio of expected variances, and therefore, the case β tending to ∞ can serve to derive general upper bounds.Quite satisfyingly, this limit case will provide a lot of simplifications. We will prove in Lemma 7, that the ratio of expected variance between ψ β and φ β can be upper bounded by the ratio of expected variance between ψ(x) and φ(x) defined asEQUATIONandEQUATIONWe present first the analysis of the ratio of expected variance for the case β tending to ∞ and then justify studying the case β → ∞ as an upper bound to the general case in Lemma 7.Lemma 6 Let ψ(x) and φ(x) be defined respectively in (3) and (4). Then, it holds thatE V ψ 1-⟨ Θ, Θ⟩ | Θ E V φ 1-⟨ Θ, Θ⟩ | Θ ≤ 9.Proof 5 We start by analyzing E V ψ 1-⟨ Θ, Θ⟩ | Θ . We note that ψ 1-⟨ Θ, Θ⟩ is equal to 1 if ⟨ Θ, Θ⟩ < 0 and is equal to 0 otherwise. To distinguish those two cases, we introduce the notation I( Θ, Θ) := 1 {⟨ Θ,Θ⟩<0} . We observe that E V ψ 1-⟨ Θ, Θ⟩ | Θ is equal to the expected variance of Bernoulli random variable with probability given by Q(Θ) := E[I( Θ, Θ)] and can therefore be written asE V ψ 1-⟨ Θ, Θ⟩ | Θ = E[Q(Θ)(1 -Q(Θ))].The last part of the proof concerns E V φ 1-⟨ Θ, Θ⟩ | Θ . Similarly, we can distinguish between two cases: either ⟨ Θ, Θ⟩> 0 and φ(1-⟨ Θ, Θ⟩) = 0, or ⟨ Θ, Θ⟩< 0 and φ(1-⟨ Θ, Θ⟩) = 1 -2⟨ Θ, Θ⟩. Introducing the notation G(θ) := E[I( Θ, Θ)⟨ Θ, Θ⟩], we can write E V φ 1-⟨ Θ, Θ⟩ | Θ = E E φ 1-⟨ Θ, Θ⟩ -E φ 1-⟨ Θ, Θ⟩ | Θ 2 | Θ = E I( Θ, Θ) 1 -2⟨ Θ, Θ⟩ -(Q(Θ) + 2G(Θ)) 2 + E 1 -I( Θ, Θ) (0 -(Q(Θ) + 2G(Θ))) 2 .Distributing the square and simplifying terms, we obtainE I( Θ, Θ) 1 -2⟨ Θ, Θ⟩ 2 -2E I( Θ, Θ) 1 -2⟨ Θ, Θ⟩ (Q(Θ) + 2G(Θ)) + E I( Θ, Θ) (Q(Θ) + 2G(Θ)) 2 + E 1 -I( Θ, Θ) (Q(Θ) + 2G(Θ)) 2 = E I( Θ, Θ) 1 -2⟨ Θ, Θ⟩ 2 -E (Q(Θ) + 2G(Θ)) 2 .To get to the last part of the proof, we rewrite explicitly Q(Θ)+2G(Θ) as E I( Θ, Θ) 1 -2⟨ Θ, Θ⟩ and optimize over the values of (1 -2⟨ Θ, Θ⟩). We can thatE I( Θ, Θ) 1 -2⟨ Θ, Θ⟩ 2 -E E I( Θ, Θ) 1 -2⟨ Θ, Θ⟩ 2 ≤ sup α∈[-1,3] E I( Θ, Θ)α 2 -E E I( Θ, Θ)α 2 = 9 • E[Q(Θ)(1 -Q(Θ))],which concludes the proof.Lemma 7 Let ψ β (x) = ϕ β (1) -ϕ(1 -x) and the logistic surrogate φ β as in Definition 2 and let ψ(x) and φ(x) be defined respectively in (3) and (4). Then, for all β > 0, it holds thatE V φ β 1 -⟨ Θ, Θ⟩ |Θ E V ψ β 1 -⟨ Θ, Θ⟩ | Θ ≤ E V φ 1 -⟨ Θ, Θ⟩ | Θ E V ψ 1 -⟨ Θ, Θ⟩ | Θ .Proof 6 Beginning with the ratio of expected variances between φ β and ψ β , we will apply a series of transformations to the functions φ β and ψ β , ultimately yielding the functions φ and ψ. These transformations are chosen to ensure that they can only increase the ratio of expected variances.By definition, the function ψ β and its surrogate φ β are identical for x ∈ [0, δ β ) and then diverge linearly at a rate of ψ β (δ β )/δ β on the interval x ∈ [δ β , 2]. We illustrate this on Figure 1 . Focusing on the domain where the two functions coincide, we observe that the transformation f (x) = max(x, ψ β (1))reduces the expected variance for both ψ β and φ β . However, since ψ β (x) is less than or equal to φ β (x) for all x ∈ [0, 2], and both functions exceed ψ β (1) on the interval [1, 2], the transformation f proportionally reduces the expected variance of ψ β more than that of φ β . As a result, the transformation increases the ratio of expected variances between the two functions. As ψ β and φ β are strictly increasing function, the resulting functions, illustrated on Figure 2 , can be written asf (ψ β (x)) = ψ β (1) x ∈ [0, 1], ψ β (x) x ∈]1, 2]andf (φ β (x)) = ψ β (1) x ∈ [0, 1], φ β (x) x ∈]1, 2].The second transformation we apply concerns only the function f (ψ β (x)). We will crop all the values larger than ψ(δ β ) by applying the transformation g(x) = min(x, ψ(δ β )). As f (ψ β (x)) is an increasing function, the function g(f (ψ β (x))), illustrated on Figure 3 , can be written asg(f (ψ β (x))) =    ψ β (1) x ∈ [0, 1], ψ β (x) x ∈]1, δ β ] ψ β (δ β ) x ∈]δ β , 2].The transformation g reduces the variance of the function as f (ψ β (x)) it both decreases the values of f (ψ β (x)) and the derivative of f (ψ β (x)) for all x ∈]δ β , 2].The third transformation we apply is increasing the value of β. As β increases, the derivative of f (φ β (x)) increases everywhere,d dx f (φ β (x)) =      0 x ∈ [0, 1], β exp(-β(1-x)) (1+exp(-β(1-x))) 2 x ∈]1, δ β ] ψ β (δ β )/δ β x ∈]δ β , 2],and the expected variance of f (φ β ) increases. Regarding g(f (ψ β (x))), we can show that that for allx ∈ [0, 2], the ratio f (φ β (x))/g(f (ψ β (x))) increases with β. Indeed, this ratio is equal to 1 for allx ∈ [0, δ β ] and increases for all x ∈]δ β , 2] asf (φ β (x)) g(f (ψ β (x))) = φ β (δ β ) + φ β (δ β )/δ β • (x -δ β ) φ β (δ β ) = 1 + (x -δ β ) δ βand as δ β is a decreasing function of β (see Remark 1), the ratio (x -δ β )/δ β is a increasing function of β for all x ∈]δ β , 2]. This fact ensures that the expected variance of g(f (ψ β (x))) cannot increase proportionally more than the expected variance of f (φ β (x)). We can therefore study the ratio of expected variances between f (φ ∞ ) and g(f (ψ ∞ )).The last operation we apply is merely a convenient shifting and scaling, h(x) = (x - We recall that ψ β (x) = ϕ β (1) -ϕ β (1 -x) and can equivalently be written asEQUATIONψ β (x) = 1 1 + exp(-β) - 1 1 + exp(-β(1 -x)).We have to distinguish between three cases for (x -1): negative, zero or positive. For values of x ∈ ]1, 2], we have that(1-x) < 0 and that lim β→∞ ψ β (x) = 1, if x = 1, we have that lim β→∞ ψ β (x) = 1/2 and for values of x ∈ [0, 1[, we have that(1 -x) > 0 and that lim β→∞ ψ β (x) = 0. We can therefore writeψ ∞ (x) =    0 x ∈ [0, 1[, 1/2 x = 1, 1 x ∈]1, 2].We can now construct the corresponding φ ∞ (x). We note that ψ∞(x)x is maximized when taking the limit to x = 1 + from the right:lim x→1 + ψ∞(x) x = 1. It comes that φ ∞ (x) can be written as φ ∞ (x) =    0 x ∈ [0, 1[ 1/2 x = 1, 1 + (x -1) x ∈]1, 2].We denote the resulting functions h(g(f (ψ ∞ (x)))) and h(f (φ ∞ (x))) respectively as ψ(x) and φ(x).We note that they can be written quite simply asψ(x) = 0 x ∈ [0, 1], 1 x ∈]1, 2],andφ(x) = 0 x ∈ [0, 1], 1 + 2(x -1) x ∈]1, 2].Remark 1 The derivative of the function ψ β (x)/x is given byd dx ψ β (x) x = 1 x d dx ψ β (x) - ψ β (x) xWe note that it is equal to zero for values ofx ∈]0, 2] such that d dx ψ β (x) = ψ β (x)x . By definition of δ β , d dx ψ β (δ β ) = ψ β (δ β )This section presents the proof of Theorem 2. One lemma, (van Handel, 2016, Lemma 5.13), will be particularly useful to control the covering number. We restate the lemma below.  



Reviews: review: title: title: Official Review of Submission34 by Reviewer UaYR
main_review: main_review: Summary:
----------
The Thompson algorithm for logistic bandits is studied under the assumption that the parameter space is included inside the action space.  A new bound on the information ratio is derived, as well as a regret bound which scales much better than previous results and is valid for a continuous action space. 

Main Review:
----------
Quality and clarity: Generally, the paper is well-written. However, I think that switching from $\theta$ to $\Theta$ causes confusion (if I understand correctly they denote the same object, the unknown model parameter).

I do not understand the last equality before l. 315. Shouldn't it be 
$$
U(\Theta) \langle \Theta, \Theta \rangle - \langle \hat{\Theta}, \Theta \rangle
= \langle U(\Theta) \Theta - \hat{\Theta}, \Theta \rangle
$$
instead of $\langle U(\Theta) \Theta, \Theta - \hat{\Theta} \rangle$?


Typos
--------
Proof 1: $\sum_{t = 1}^{T}$ missing before 221.
Proof 2: In the formula after line 276, the inequality is written the wrong way around.
Lemma 8: missing | after the covering number for $\epsilon \ge 1$.
Proof 7: in the last inequality, it should be $2 \beta T / d$ instead of $2 \beta T / \beta$.
Remark 1: full stop missing after the formula after l. 392. Left-over words in l. 394.
The $(x)$ in ll. 331, 335, 349 are superfluous.
l. 361: "functions" instead of "function".
l. 366: should be instead (I think) "$f(\psi_{\beta}(x))$ as it".

Citations
--------
Citation "Information Theory - From Coding to Learning" outdated: one author missing, correct year should be 2024.
For Russo, Van Roy - "An Information-Theoretic Analysis of Thompson Sampling", please cite the version published in JMLR.
Similarly, Russo, Van Roy - "Learning to Optimize via Informationen-Directed Sampling" has been published in NeurIPS, Faury et. al's paper in PMLR, Dong and Van Roy's paper in NIPS'18 etc. (I didn't do through the other arXiv citations).

Minor mathematical stuff
---------
Proof 2: first you define $h_2$ on (0, 1), but then plug in values in [0, 1] into it in line 275. One can extend $h_2$ by $0$ onto $[0, 1]$, however and consider one-sided derivatives at the endpoint, but right now you are mixing both concepts.
In line 273 it should instead say "$\xi$ in between $x$ and $p$". Since $x$ could be larger than $p$, and then $(x, p)$ is empty. 
In line 276, I recommend instead writing "for $x = U(\omega)$ and $p = \mathbb{E}[U]$ for $\omega \in \Omega$" to be more precise. Then the inequality holds for all $\omega \in \Omega$ and taking the expectation then yields the next formula, as desired.
Also, according to my experience, the Shannon entropy is defined with respect to $\log_2$ instead of $\ln$, and in that case, your derivative of $h_2$ is of by a multiplicative factor (which hence does not impede the proof at all).


Other comments / wording
--------
In line 52, I would write "scales only logarithmically with" instead of "on".
In line 10, I would write "regret bound of" instead of "in" (agreeing with other similar formulations in the rest).
Why do you use http:// instead of https:// for the arXiv links?
Also the formatting (e.g. when italics are used) is not entirely consistent, compare for example lines 202-203 with 205-206.
title: title: A Rigorous Theoretical Analysis of Thompson Sampling for Logistic Bandits, But Lacking Practical Validation
main_review: main_review: The authors present a well-structured analysis of Thompson Sampling algorithm for logistic bandits. It focuses on a refined information-theoretical approach which is built upon previous works relevant to Thompson Sampling by improving regret bounds. Compared to previous works, it aims to address the exponential dependence on the slope parameter with the mathematical proof. The proposed regret bounds provide a better theoretical understanding of Thompson Sampling for logistic bandits. 

However, although the pre-defined problem, algorithms, and theoretical derivations are explained step by step, the current version lacks convincing results based on numerical demonstrations. To broaden the readership, the authors are strongly suggested to devise numerical simulation examples to demonstrate their claims, as well as providing simulation scripts for the numerical examples with clear step-by-step comments. Otherwise, this kind of mathematical derivation is hardly to be useful for the broad readership of the booming community.

In a word, the current version contribution to the community would be incremental due to its complexity and limited numerical validation, which could hamper for a broader readership or practical implementation for such theoretical proposal. The authors are expected to revise accordingly.