An Information-Theoretic Analysis of Thompson Sampling for Logistic Bandit Problems
Authors: Amaury Gouverneur
Tobias Oechtering
Mikael Skoglund
Venue: Accepted by TMLR ()

Abstract: We study the performance of the Thompson Sampling algorithm for logistic bandit problems. In this setting, an 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 parameter $\beta>0$, and both the action $a\in \mathcal{A}$ and the unknown parameter $\theta \in \mathcal{O}$ lie within the $d$-dimensional unit ball. Adopting the information-theoretic framework introduced by Russo & Van Roy (2016), we derive regret bounds via the analysis of the information ratio, a statistic that quantifies the trade-off between the immediate regret incurred by the agent and the information it just gained about the parameter $\theta$. We improve upon previous results and establish that the information ratio is bounded by $d(4/\alpha)^2$, where $d$ is the dimension of the problem and $\alpha$ is a \emph{minimax measure} of the alignment between the action space $\mathcal{A}$ and the parameter space $\mathcal{O}$. Notably, our bound does not scale exponentially with the logistic slope and is independent of the cardinality of the action and parameter spaces. Using this result, we derive a bound on the Thompson Sampling expected regret of order $O(d \alpha^{-1} \sqrt{T \log(\beta T/d)})$, where $T$ is the number of time steps. To our knowledge, this is the first regret bound for any logistic bandit algorithm that avoids any exponential scaling with $\beta$ and is independent of the number of actions. In particular, when the parameters are on the sphere and the action space contains the parameter space, the expected regret bound is of order $O(d \sqrt{T \log(\beta T/d)})$.

Published in Transactions on Machine Learning Research (02/2026)
An Information-Thhoreee Analysis of Thompson Sampling for Logistic Bandit Problems
Amaury Gouverneur
amauryg@ithh.s
Division of Information Science and Engineering (ISE)
KTH Royal Institute of Technology
Stockholm, Sweden
Tobias J. Occhtcring
occh@kth.se
Division of Information Science and Engineering (ISE)
KTH Royal Institute of Technology
Stockholm, Sweden
Mikael Skoglund
skoglund@kk
Division of Information Science and Engineering (ISE)
KTH Royal Institute of Technology Stockholm, Sweden
Reviewed on OpenReview: https: // openreview. net/ forum? ? id= 94y6Xf:J71
Abstract
We study the performance of the Thompson Sampling algorithm for logistic bandit problems. In this setting, an agent receives binary rewards with probabilities determined by a logistic function, exp(Kaa 0)) + exp( f))), with parameter 3 0, and both the action E A and the unknown parameter E O lie within the d-dimensional unit ball. Adopting the informatiion-thorreiii framework introduced by Russo & Van Roy (2016), derive regret bounds via the analysis of the information ratio, statistic that quantifies the trade-off between the immediate regret incurred by the agent and the information it just gained about the parameter 0. We improve upon previous results and establish that the information ratio is bounded by d(4/a)?, where the dimension of the problem and a is a minimar measure of the alignment between the action space A and the parameter space O, Notably, our bound does not scale exponentially with the logistic slope and is independent of the cardinality of the action and parameter spaces. Using this result, we derive bound the Thompson Sampling expected regret of order O(da 'VT log(3T/d), where T is the number of time steps. To our knowledge, this is the first regret bound for any logistic bandit algorithm that avoids any exponential scaling with 3 and is independent of the number of actions. In particular, when the parameters are on the sphere and the action space contains the parameter space, the expected regret bound is of order Old (Tg((3/d))
1 Introduction
This paper studies the logistic bandit problem, where agent sequentially interacts with an unknown environment with parameter 0 O. At each time step, the agent selects action A and receives binary reward whose probability of being one is given by the logistic function exp(3<a, 0)) + <x,( f))) with slope parameter B > 0. In this setting, both the action space and the parameter space are closed bounded subsets the d-dimensional real space Ed. The goal of the agent is to maximize its total reward, or equivalently minimize regret, that is, the difference between the optimal cumulative reward and the cumulative reward achieved by the agent. This setting is used to model various scenarios, such as click- through rate prediction, spam email detection, and personalized idveeni (Chapelle Li 2011 Russo

---

Published in Transactions on Machine Learning Research (02/2026)
& Van Roy 2018) Beyond these examples, bandit-based decision systems are also used in news and content
recommendation, dynamic pricing, information retrieval, and healthcare (see Bouneffouf et al. (2020) for a survey of the different applications, and Li et al. (2010) for a large-scale deployment).
The performance, or regret, of algorithms for logistic bandits has been extensively studied, with significant contributions including analyses of Upper Confidence Bound (UCB) algorithms (Filippi et al.] 2010 Li
et al. 2017 Faury al. 2020) as well as the study of Thompson Sampling (TS) (Russo & Van Roy Dong et al. 2019 Abeille & Lazaric 2017). However, all existing regret bounds for logistic bandits exhibit an exponential dependence the parameter B (see Table I or scale poorly with the mumber of actions. Those results are unsatisfactory because, in practice, the distinction between ncar-optimal and sub- optimal actions gets more pronounced as 3 increases, which can make it easier to find near-oplimal actions. Similarly, algorithms like TS have demonstrated strong empirical performance even in problems with large or continuous action spaces (Russo Van Roy 2014). This gap between theoretical bounds and empirical behavior was already pointed out by McMahan & Streeter (2012), who called for improved regret analyses in the logistic bandil. selting, challenge that has long remained open.
2014
In this work, we focus the Thompson Sampling algorithm [Thompson 1933). which, despite its simplicity, has proven to be effective for wide range of problems (Russo et al. 2018 Chapelle & Li 2011p. Analyzing the TS expected regret, Russo& & Van Roy (2016) roduced the concept of the information ratio, defined as the ratio between the squared expected instantaneous regret and the information gained about the optimal action from the current observation. Building on this framework, Dong & Van Roy (2018) derived a near-optimal regret rate of O(d'TT log T) for d-dimensional linear bandit problems. However, applying this analysis to the logistic setting yields regret bounds that grow exponentially with the parameter (see Appendix E]. Using nunerical simulations, they conjectured that the TS information ratio for logistic bandits scales linearly with the problem's 's dimension d and is independent of the slope parameter 33 and the cardinality of the action and Conjecture 1).
parameter spaces (Dong & Van Roy 2018
Table 1: Comparison of various regret guarantees for the logistic bandit, problem.
A Aggorithm
Regret Upper Bound
Note
Thompson Sampling
O (e d. T1/2 1og()))/2)
Bayesian bound
Russo & Van Roy
2014
GLM-TSL
O (ef /.// log(d) /2. log(T))/3)
Frequentist bound
(Abeille & Lazaric
2017
GLM-TSL
O (6 d. T1/2 log(T) el od log(?)))
Frequentist bound
Kveton et al.
2020
Logistio- UC
B--
0 (d- 1o/2.oog(T) + e de log(T))))
Frequentist bound
Faury et al.
2020
Thompson Sampling
(377)))
Bayesian bound
(Neu et al. 2022
Thompson Sampling
Bayesian bound, a independent of /
O (d- 1 T1/2 log(8T
(this paper)
Studying specifically the TS regret for logistic bandits, Dong et al 2019 introduced two statistics to characterize the sets A and O the minimaz aligument constand a = mingeo Aa, f) and the fragility d n, which is the cardinality of the largest subset of parameters such that their corresponding optimal action is "misaligned" (i.e. the inner product is negative) with any other parameter from the subset. Using those statistics, they state the TS information ratio is bounded by 100 max(d, n) This result is unsatisfying as in general, the fragility dimension can grow exponentially with the dimension d, but more problematic, their regret analysis is incorrect as it relies on the rate-distortion bound from Dong & Van Roy (2018), which is incompatible with a bound on the TS information ratio. Additionally, their analysis of the information ratio bound is only rigorous for 3 & 2 as relies on an unproven inequality for larger values of 3. We elaborate in more detail on these gaps in Appendix F
This statistic referred as the worst-case optimal log-odds the work of Dong al. 2019
2Te definition can be found in Dong al. (201 Definition 2).
2

---

Published in Transactions on Machine Learning Research (02/2026)
In this paper, address the above limitations and obtain regret bound for logistic bandits that scales linearly in the problem dimension d while not scaling exponentially with 3 or depending on the cardinality of the action and parameter spaces. Importantly, our bound does not require introducing the fragility dimension. Our main contributions are as follows:
We prove an commmatioo-tchorttie regret bound of order Ol OlVTT(H(()))+ + (ETT)) that holds for infinite and continuous action and parameter spaces. The bound relies on H())), the entropy of the parameter quantized at scale E, and on the average expected TS information ratio, r.
We present, a new analysis showing that, for all B > O, the TS information ratio for logistic bandits is bounded by d(4/a)² where a is a minimaz alignment constant between A and O which is defined as a = mingeo A f). Notably, our bound does not depend on the fragility dimension.
We prove regret bound of order this is the first regret bound for any logistic bandit algorithm that does not scale exponentially with 3 and is independent of the number actions [A].
for Thompson Sampling, To our knowledge,
Additionally, we show that if the parameters are on the sphere and the action space encompasses the parameter space, the expected regret of Thompson Sampling is bounded in (dd (ogg (BT)
These results help to explain the empirical performance of Thompson Sampling in logistic bandit problems across different logistic regimes and for large or continuous action spaces, and they highlight the importance of aligument between the action and parameter spaces.
The rest of the paper is organized as follows. Section 2 introduces the logistic bandit problem, defines the Bayesian expected regret, and the specific notation used. In Scction 3 we introduce the Thompson Sampling algorithm and the information ratio analysis. Section states and discusses our main results, providing improved regret. bounds. Section 5 presents the key ideas for analyzing the information ratio. Then Section illustrates the improvement of our bounds compared to previous regret guarantees through D
numerical experiments; and finally, Section i
discusses our results and future extensions.
Throughout the paper, we write random variables with capital letters (e.g. X), their realization with low- ercase letters (e.g. x), and their outcome space calligraphic letters (e.g., X).
2 Problem Setup
In the logistic bandit, an agent interacts sequentially with an environment that is characterizod by an unknown parameter 0 O Red, At each time step L (1...., 77,, the agent selects an action E A S Rd and receives a random reward RG E (0, sampled from Bernoulli distribution with probability given by a logistic function applied to the inner product (a,6),
exp(3Ka,0))
R₁ Bern
1 exp( (3, 0))
where 3 > is a scale parameter known to the agent. For the rest of the paper, we denote the logistic function as
exp(Bx) (5(x)= == 1 exp(3r)
In this setting, the action space A and the parameter space O are compact subscts of Rd and, without loss of generality we assume that A and O lie within the d-dimensional Euclidean unit ball, B₂ 1). For a given action space A and parameter space O, we define their minimaz aligmment constant a == mineeo max 0). Intuitively, it quantifies how well the action set covers for any of the possi- ble parameters: a value of a close to indicates that, for any parameter, there exists an action that aligns
3hiis setting is equivalent to the one considered by Faury et 2020 using > maximal norm for 0
3

---

Published in Transactions on Machine Learning Research (02/2020)
well with it, whereas value close to 0 means that there exists a parameter at best nearly orthogonal to all actions. In the rest of the paper, we assume that the action and parameter spaces are such that > 0. This assumption is mild. It is already satisfied if the set A contains two opposite actions a and a' (i.e., a = -d') which ensures a 2 for any paramoter set O.
Following the Bayesian framework, we assume the parameter vector E O sampled from a known prior distribution Pe. At time step & E (I,...,T), the agent selects an action A, based on the past observations according some possibly stochastic decision policy. As the reward distribution depends only the selected action and the parameter, the random reward R& is also written R(A,, (), where R A x O {0, 1) is stochastic process defined such that R(a, 0) ~ Bern
(on((a((( ((, (a),()))))) 0)))
The goal of the agent is to sequentially select actions that maximize the total expected reward, or equivalently, that minimize the total expected regret defined as:
T Σ
E B[Regret(T)) E R(A R(A,,))) -
where A is the optimal action corresponding to the parameter O, that is, we set A = arg max E[R(a, 0)]. We define the mapping (0): := arg max as E[ [[R( ()] so that we can write A = T.( I
3 Thompson Sampling and the Information Ratio
Thompson Sampling is an elegant algorithm for solving bandit problems. Tt works by randomly selecting actions according to the posterior probability of being optimal. More specifically, at each time step e {1.....T) T), the agent samples a parameter estimate ô, from the posterior distribution of θ, conditioned on the history H' and selects the action that is optimal for the sampled parameter estimate, A, (,,)). The pscudocode for the algorithm is given in Algorithm [ Since the o-algebras generated by the history are often used in conditioning, we introduce the notation E.[-] E[-|H'] to denote the conditional expectation given the history H¹
Algorithm Thompson Sampling algorithm
Input: parameter prior IPe, mapping m..
for t= 1 to T do
Sample parameter estimate ê Pojr.
4: Take the corresponding optimal action A, n. (Ô.).
5: Collect the reward R. = R[A,, 0).
6: Update the history H = H² u R.).
7: end for
The information ratio, originally introduced by Russo & Van Roy (016)) quantifics the trade-off between exploration and exploitation. In this paper, we define the information ratio at time as the ratio between the squared instantaneous expected regret and the information gaèned about the environment parameter,
r. E, 9) R(A,,
((A,)),,)) θ,)
where L(O; θ,) = [DLLL E. R. n. (.n.,,,,)) 6.) is the mutual information between the param- eter O and the observed pair R2, θr given the histor H'
This ratio measures the trade-off between minimizing the current squared regret and gathering information about the parameter θ; a small ratio indicates that a substantial gain of information compensates for any significant regret.
'If multiple actions optimal for given parameter, arbitrarily fix the mapping for that paramcter one of the optimal actions. The mapping me is therefore well-defined function. This quantity is sometimes referred the disintegrated madual information, for example Negrea
2019
4

---

Published in Transactions on Machine Learning Research (02/2026)
4 Main Results
This section presents main results the Thompson Sampling regret for logistic bandits. In Theorem 2 we prove an information-theortti regret bound for logistic bandits that holds for continuous and infinite parameter spaces. Then, in Proposition ! we present our key result, bound on the TS information ratio that depends only on the problem's dimension and on the minimax alignment constant a. By combining this result with our regret bound, we derive our main contribution in Theorem 5 a bound on the expected regret of TS for logistic bandits, which scales as O(d/av (oT()))
Our first thcorem provides regret bound that holds for large and continuous action spaces. It relics the entropy of the quantized parameter Oe, which is the closest approximation to @ on g-net in the Euclidean space (O, ll-112). It builds on Gouverneur et al. (2023 Theorem 2) and Neu et al. (2022
Theorem 2) and improves their results for the logistic bandit setting. The proof of Theorem 2 relies on approximating the conditional mutual information I(@; Re( H²) with I(O,; R2 (., and bounding the remainder using a Taylor expansion. Importantly, and in contrast. to Dong & Van Roy (2018) Theorem 1), this result is compatible with bounds on the information ratio of Thompson Sampling, rather than the "one-slep compressed Thompson Sampling" This distinction crucial as it resolves the incompatibility that arises in the regret analysis of Dong et al. 2019 (c.f. Appendix
Definition 1 Let the set Og be an E-net for 11-12) with projection mapping : :::- - O2 such that for all E O we have 10 - q(0)]l2 & E. We define the quantized parameter as O := (
Theorem 2 For all 3 > 0, under the logistic bandit setting with logistic function (s(x), let the quantized parameter +e be defined as in Definition 1 for any E [0, If the average expected TS information ratio is bounded, T D [T & T, for some r > 0, then the TS regret is bounded as
E [eegret(()) & IT (H(O.) + 322
Proof 3 We start by rewriting the TS expected regret using the information ratio:
E Regret(TT) E[R(A',)) RRA,, 0) Σ E V RL, 0),
Applying Cauchy--Shhan Schwarz for expectations, E[VXVY the sum, we obtain
E followed by Schwwarz over
T <
T
E R(eegret(T)
(), & IT I R(A, 0),
where in the last step, we used that by assumption ΣT E[T,] & IT. Then, by the chain rule for matual information (Polyanskiy & Wu. 2025 Theorem 3.7.b) we write.
I(0; R(A, 0), 0), I(0,0, + I(O) R(A, H) 6.) I(0; R(A, H) using that O and & are independent given H², and that 1(0; 1(:0,,H') 0.
Let P R.jm& e. and P R denote the distribution of R₂ conditioned respectively on H' O O and H'. Ô.
Then, we have that
P PR. é, (Rt) log PP PR.HH 6, (Re)
11.
[OH ,,,) E EH,,,,,,
,, En
En. -2 mi
(2)
where we used that P 6.,, P P since Rd is independent of He conditioned on O and θ.
5

---

Published in Transactions on Machine Learning Research (02/2026)
Let Oe be E-net for (--12) with mapping 9 : - O2, and define O₂ == (() the quantised porameter.
We introduce P Re|H ,,, to denote the posterior reward distribution given H', Ue Oc, which is oblained by
averaging over all O' such that q(O') = E, that is P RRA a.. = R. () (1000).....
Then, starting from the definition of conditional mutual information, add and subtract the log- bog-probability log IP n. (Be) inside the inner expectation to oblain
ERPPRR log PRI 1.,0, (Re) IP PRIMI&G (Re)
P PR. (Ba) log P b.. (R,) ]1
(R)
2 = E nr 0.6.
+ ERR BRR-FRRee e
Using the law of total expectation, the outer expectation over 2 may be replaced by one over Oe, and the first term is exactly the conditional mutual information 1(02; R4 H θ,). We recognize the second term as the expected KL divergence between the true reward distribution n and the quasttize posterior IP RRIno,, which by converity of the KL divergence is most the average over the quantization:
E e. [PKL e P PRI = Es,e, [E [E[DKL(PRIje..r (P I (R.
((09)),,)))
Conditioned on Q = 0, O² 0, and θ = d,, we let 17 1= (T,))),, we can write n/ = (T.) 8¹). We then have that o/ + x for some I E [-22, 2c]. Indeed we have
K (o.(0),0)) (T. (0)) < (0.)) 10 0' 1 (10 {(0) + -19((0) 10ll) $ 22,
where we used the fact that A Ba(O, 1), the triangle inequality and the definition of q()). We can then write the inner KL divergence as
Φo(n) ) (1 +5((1) log 1- ()(()(
D(x) ( log 25(1+ + x)
25(1)) x))
Differentiating with respect to x, and using that d(xx)= is D'xx) (( + x)- (n))) and the second derivative is D* 8 + x) Φ1( + x))
we have that the first derivative
< 8²
Since D(0) = 0 and (0) = 0, we can use Taylor's remainder theorem and get that
(K - - DD())= D(x) S (x- ( (t)dt
1 32 <
x² 1 33..9
4 2
Summing over t and applying the chain rule for conditional mutual information, we obtain
T IH,,) I(0,; HT) < H(O)).
I(o (.)
Collecting the 3² terms and inserting the above bound into eq.
yields
E [eggrett(T)] < IT (H(O.)+ (1)0))++88:77))
which is the desired result.
In the following, we present an important proposition; we prove an upper bound on the TS information ratio that depends only on the problem dimension d and the minimax aligument constant a. Notably, this upper bound is independent of the logistic slope B > 0 well of the cardinality of the action and parameter spaces, and depends linearly on the the problem's dimension d. Those properties were anticipated in Dong & Van Roy (2018] Conjecture 1).
Proposition 4 For all B > O, and for all A, S 1a(0, with minimas alignement constant a, under the logistic bandit setting, with logistic function (x),, the TS information ratio bounded as
16d
T2 x a
6

---

Published in Transactions on Machine Learning Research (02/2026)
The dependence on 1/a should not be surprising: when the action and parameter spaces are poorly aligned, that is when is small, it is possible to construct an action space A and parameter space O such that the parameter vectors are nearly orthogonal to all actions (see Dong et al. (2019) Appendix D)). In such case, the reward probabilities associated with different actions become almost indistinguishable, so obscrving the reward provides little information about the environment, which in turn leads to larger information ratios.
The proof techniques used for Proposition f build upon and innovate over prior work in two key ways. Our first innovation is to control the information ratio by relating both regret and information gain to the expected variance of the regret, conditioned on the sampled parameter; lower bounding the information gain using the regret variance instead of the regret expectation as in Russo & Van Roy (2016) or Dong & Van Roy (2018). which makes it possible to avoid scaling with the smallest slope of the logistic function which decreases exponentially with the parameter 3. Our second innovation is to show that the limit case 8 - o can serve as uniform upper bound, thereby simplifying the analysis. We present the main ideas of the proof techniques in Scction and provide the detailed proof in Appendix B and Appendix C
Combining Proposition with Theorem 2 obtain main result: bound the expected TS regret in log(///dd) To the best of our knowledge, this is the first regret bound for any logistic bandit algorithm that does not scale exponentially with the logistic function's parameter B or with the problem dimension d and remains independent of the number of actions.
Theorem 5 For any B > O, and for all 0 S Ba(0, 1) with minimaz alignment constant >> 0, under the logistic bandit setting with logistic function dz(z), the TS regret is bounded as
4d E[Regret & a
T 2d
T log + 6
Proof 6 Combining Theorem with Proposition 4 we upper bound the entropy H(Oz) by the cardinality of the e-net to get regret bound of 4f \ dT (Iog([@zl) + 3 To define Oe, set O as the 8-nel of smallest cardinality. As the parameter space O is within the Euclidean unit ball, we use Lemma 23 to control the covering number, log([O=l) & d + 2/E), and upper bound the TS regret as
E[Regret (T)] < 4/a//d dr doog 1+
2 E)
+ 2
Finally, setting e = /2d/ BPT and rearranging terms inside the logarithm yields the desired result.
Remarkably, our result does not depend on the fragility dimension n). This important as, except in the case where a = the fragility dimension can grow exponentially with the problem dimension d (see Dong et al. 2019 Remark 3)). In general, the dependence on cannot be removed; as shown by Dong et al. (2019) Proposition 11), there cannot be an a-indeppnnent upper bound that is polynomial in d and sublincar in T.
Nevertheless, the following corollaries identify specific settings where this dependence on the minimax align- ment constant a disappears. We illustrate the improvement of Corollary 7 over previous works through numerical experiments on a synthetic logistic bandit problem. The results are presented in Section
Corollary 7 For any 3, under the logistic bandit. selding with logistic function Φ5(#), let A S B,(0, 1) and O c Sa 1) be such that O = A. Then the TS regret is bounded as
T 2d
E [[egret((T) (T)] < 2d, Tlog 3 63 636
Proof 8 O = 1) and if = A, then for each E O, there erists an action E such that a 0 and (a, 8) 1, implying In this setting, we can use a tighter bound on the information, I, 4d/a²
presented in Section 0 Using this result. logether with Theorem as in Theorem 5 concludes the proof.

---

Published in Transactions on Machine Learning Research (02/2026)
Corollary 9 For any B, under the logistic bandit setting with logistic function dg(x), there erists action space A with [A] & 2d 3 such that for any O = Sa(O, 1), the TS vegret is bounded
T B (R)gret(()) & sd Toog 3+ 636 2d
Proof 10 Starting from Theorem 5 we have to construct A such that its minimar aligrement constant or is greater than or equal to for any s Sa(O, 1). This is satisfied if A is a I-net for S,(0, 1). Setting as the --net of minimal cardinality, from Lemma 24 we have |A| & 2d 2d-33-1,
In the above corollaries, the regret bound matches the (d minimax lower bound for linear bandits of Dani et al. (2008), up logarithmic factors. Moreover, its dependence and vT aligns with the instance-dependent lower bound of Abeille al. (2021), implying that the bound is tight in both d and T up to logarithmic and problem-dependent constants.
5 Analysis
This section presents the key ideas underlying the proof our main proposition, Proposition For simplicity and clarity exposition, we focus first on the specific setting of Corollary 7 which corresponds to the case where 1. The generalization of these arguments to arbitrary parameter and action spaces follows the same rcasoning but requires additional notation and handling the misalignment between the parameter and action spaces. This extension is deferred to Appendix C
The proof is organized into three parts: Section 5. presents lower bound on the mutual information via the variance of reward probability; Section 5.2 proves an upper bound on the squared expected regret using a surrogate logistic function; and finally Section 5.3 explains how we derive a general upper bound on the ratio of expected variances and use the limit case
oo to prove a uniform upper bound over 8 8>1 0.
To lighten notation, omit the subscript for the remainder of the section. We recall that under the logistic bandit setting with logistic function Φ3. the reward R(Á, θ) is sampled according to Bernoulli distribution with probability Φs((Á, θ)). We introduce the notation Bern(cs θ))) to make the setting more explicit. With this notation, the information ratio can be written
(A, [[ (A 0)))
T(O) (em((
5.1 Lower bounding the mutual information via the variance reward probability
We start by stating a useful lemma that relates the variance of a [o, random variable the mutual information between U and Bernoulli outcome with probability U. The proof is presented in Appendix A
Lemma 11 Let U be random variable taking values in [0,1] and Bern(U) be Bernoulli random variable with probability U. Then it holds that
I(U; Bern(U)) 2V(U).
Using Lemma I we prove in Lemma 12 that the information that the agent gained about the parameter, T(O; (er Ô), is at least twice the expected variance of reward probability E[V[os((A, [)]]
Lemma 12 Let the logistic function be dg(x), then, for Thompson Sampling, it holds that
I(O; Bern(e:: (z 2E V ())((A
8

---

Published in Transactions on Machine Learning Research (02/2026)
Proof 13 We start by opplying the chain rule. It follows that
I(0; (e)))(((((((A))))
+ (1 (4)))) (
① I(0; Ber(())))((A 6)
B[I(os((TT (6), 9));
()))) 6).
where (i) follows from the chain-rule; (i) follows as θ and ê are independent conditioned on the history; and (k) follows from condilioning on θ and opplying the data processing inequality. Finally, applying Lemma with (0 (0), θ)) in place of the random variable U yields the desired result.
Intuitively, if the expected variance of reward probability is high, the agent is still exploring new actions and gathering information about the parameter O. In such cases, although the instantaneous regret may remain large, the agent continues to learn about the environment, which can allow the information ratio be controlled. If the expected variance of reward probability is low, we need show that the agent has identified near-optimal actions and is now incuring small instantaneous regrets. Thus the next part of the proof, Section 5.2] will be focused making this intuition rigourous by relating the expected instantaneous regret to the expected variance of reward probability.
5.2 Upper bounding the squared expected regret using the expected regret surrogate function
This part builds on and improves upon the analysis techniques of Dong et al. 2019 Theorem 5) and similar to them, the following two lemmata will be important to our proof. We restate their proofs in Appendix A
Lemma 14 Let U, V be random vectors in Rdd, and let U, V be independent random variables with distribu- tions equal respectively to the marginals of U. v, then it holds that
B B[UTV] & d. B.d.B((TT)) [(OTT)
R, be such that f(0) > 0 and S(S)/C is non-decreasing over ( > 0. Then, for any non-negative random variable U, it holds that
Lemma 15 Let R.
[[((U)) B
V[((U)
V(01
The two lemmata above will be key to relating the expected instantancous regret to the expected variance of the reward probability. Afler conditioning on the sampled Thompson Sampling parameter θ, we will express the expected regret as function of Ô and apply Lemma 15 to relate it to the regret variance. We will then use Lemma 14 to decouple inner-product terms and reveal the dependence on the dimension d. Before doing so, however, we introduce additional notation and a few reformulations to make Lemma 15 applicable.
Under the assumptions of Corollary 7 for each 0 O, there exists an action e A such that (a.
This implies that the expected regret can be written as ds((A", θ)) (a((A,,)) = Φs(1) - Φs((A, Q)). As this quantity will come up often in the analysis, (a(1)= (1 x)). We can then write the expected regret as a function of the difference between the optimal and achieved inner products, as As((A,, θ) (A, 0)) = (s ()) - ( θ))
introduce the expected regret function As(x) =
Importantly, the expected regret function As(x) applied to the difference of inner products (A (A, θ) maps the interval [0, 2] to [0, 1], and respects As( = (1) Φ3(1 - 0) = 0. thus meeting the first two conditions from Lerna 15 However, it does not satisly the third condition, as A < first increases, then reaches a maximum between 1 and 2, and finally decreases (see Appendix D and Figure 5). To address this issuc, similarly to Dong et al. (2019) B.2. Proof of (18)), we introduce a modified function, referred as the expected regret surrogate, which serves the tightest upper bound on As(a)) satisfying the last requirement from Lemma 15 The functions Ag and Ag are illustrated in Figure
9

---

Published in Transactions on Machine Learning Research (02/2026)
Definition 16 (Expected regret surrogate) We construct the expected regret surrogate function Az(x) the lightest upper bound Ax(x) such that 2 is non-decreasing over > 0.
Numely, let 6ø arg (002)
As(z) we define A as
As(x) As(dg) + +x - (x)) -2)(5))))
[0, 0g] e ]6
As(x)
where we used that (6))))) An(5g)/5g.
We are now equipped to state and prove an upper bound on the squared expected regret using the surrogate function.
1.5
3
10
1.5
3- 10
25
25
0.3
0.5
Figure Illustration of the function As (in solid line) and the function Ag (in dotted line) for dif- ferent values of B.
Figure Illustraaton of the function f As (in solid line) and the function Gg (in dotted line) for
different values of 3 used in the proof of Lemma 19
Lemma 17 Let the expected regret surrogate be defined as in Definition 16
Then, it holds that
[[Bern(ds((A",, ())) (eee((en(s(A,,)) ())) & 2d DE V
(A, (1- 16]]
Proof 18 Inlegraling over the Bernoulli oulcome, the squared expected regrel can be expressed θ) - (A.(())))))))) = 11 (A, Since by definition As(x) > Ag(x) i O, we have @)) We now apply Lemma 15 and obtain
E E (
v A
0)
(A. [6]
B[ (A, 0]] < E
E 1
- (A, θ) è
=0(())
= ( θ) (A", )) -A",
E (U(( 6>)²
We continue by applying Lemma 14 with U=U(()A and V= + and get
(U( 6)}² < d- (U
- U())² (A.0-))10))
V
A 1 (1-
22 (A, 6]
E.
V - () 9) 6
2d E
V
A
1 (A. 9)) 16|1.
10

---

Published in Transactions on Machine Learning Research (02/2026)
where (i) follows
E
- EK 6)
( = θ) éj.
Finally rearranging the terms gives the claimed result.
Combining Lemma 12 and Lemma
get that the information ratio I' is bounded by
E
V
1 - (A, 16
D d
[ (A, 6
E
A
6 by definition of As. We are close to obtain- ing a bound on the TS information ratio that is linear d and independent of and of the cardinality of the action and parameter spaces. We still have control the ratio of expected variances between As and g, we could not apply Lemma 15 directly on Ag and had work instead with its surrogate Ag.
where we use that V (e,
(A, -v
5.3 Bounding the ratio of expected variances over the functions As and Ag
The last part of the proof lakes care of controlling the ratio of expected variances between the regret probability function Ag and expected regret surrogate Åg. The full proof is presented in Appendix B
Lemma 19 Let As(x) = (1(1) - ds((1 - x) and its surrogate Ag as in Definition 16 Then, for all B > 0, it holds that
E E
V
(A, 9) (A, θ) è
1
$
A
Sketch of proof The proof starts by observing that the functions Ag and A are equal on the interval [0, 5g], and then diverge at most at a rale A'(65)). To control this divergence, we introduce the function
Ga(æ) (x - 53) (5(5)) for x E [5g. 2], and is equal to zero over [0, 6g] We show that
E
(A, 2)) 1 (A, 0)) 60]
E V
(A, 9)) + A (1 (A, 6)) 6
Ge
& 1
Next, apply cropping function fa(x) min( (s(g)) x) to the function Ap(x), contracting the squared difference (Ag(z) - A for every x, y E [0, and thus reducing the expected variance. The functions Ig o Ag and G3 are illustrated in Figure 2 After expressing the expecled variances as the expecled squared difference over the variable (Ô) θ) and ()) O) where Ô O θ are i.i.d., consider any triplet (0o, 01,02): Marimizing the ratio can be reduced a convex optimization problem, and we get that the ratio of expected variances between Gg and fa o Ag is less than or equal to (2 - 2/)3//8. This ratio can be controlled by the asymptotic case 3 - 20 and is smaller than or equal to 4 (see Appendin DV. Pinally, plugging this result into the above inequality gives the claimed result.
Oo, 01, O2 O and bound the worst-case rutio for
11

---

Published in Transactions on Machine Learning Research (02/2026)
6 Numerical Experiments
To illustrate the improvement of our regret analysis compared to previous works, we perform numerical experiments on a synthetic problem. We consider a logistic bandit problem in dimension d = 10, with time horizon = 200, and with slope parameter 3 ranging from 0.25 to 10. For both action space and parameter space, we use the closed d-dimensional unit sphere, distribution for the paramcter O. We compute the expected regret of the Thompson Sampling algorithm using an MCMC method and compare it to three Bayesian regret. bounds that hold for continuous spaces: our Corollary Russo & Van Roy/ 2014 Proposition 10) and Dong et al. (2019) Proposition 17) adapted to be compatible with Dong & Van Roy
O S, 1) and assume uniform prior
2018 Theorem 1) (see Appendix El.
The results are presented Figure 3 The left sub-figure shows the evolution the expected regret and the regret bounds for two different logistic function values, 3 E 42, For both values, our bound remains tighter across the entire horizon and is less sensitive increasing 3. The right sub-figure compares the different regret bounds T 200 for [0.25, 10]. We observe that our bound is competitive across the whole range and quickly becomes orders of magnitude tighter. Importantly,
observe that while bound increases only logarithuiiaally both Russo & Van Roy (2014) Proposition 10) and Dong et al. (2019 Proposition 17) grow exponentially with 3 and quickly become vacuous. We note that the expected regret decreases for larger B. This was anticipated since, for large values of B3, the distinction between near-optimal and suboptimal actions becomes more pronounced, facilitating the identification of ncar-optimal actions.
Russo & Van Roy, 2014 This paper
Dong Van Roy, 2018
Thompson Sampling
10a0
T 200
10s
Regret (log (og-scale)
10
10a
10
10a
10
10a
10a
10
100
150
200
10
T
Figure 3: The left sub-figure compares the evolution of the bounds and the expected regret with the time steps T' for 3 (2, The right sub-figure illustrates the behavior of the bounds and the expected regret time T = 200 for values of 3 ranging in [0.25, 10).
7 Conclusion and Future Work
In this work, we analyze the performance of the Thompson Sampling algorithm for logistic bandit problems. In this setting, the agent sequentially selects actions e A Rd and receives binary rewards with probability given by logistic function exp(8(a, ()) 0))), with slope parameter and unknown parameter I e O Dccl Rd. Building on the information-theoreti framework from Russo & Van Roy (2016), we study the information ratio, a key statistic that captures the trade-off between exploration and exploitation in bandit problems. We show that the information ratio of Thompson Sampling for logistic bandits can be bounded using only the dimension of the problem, d, and a, the minimax constant mcasuring the alignment between the action and parameter spaces. Importantly, our bound is independent of the slope parameter B and of the cardinality of the action and parameter spaces.
12

---

Published in Transactions on Machine Learning Research (02/2026)
Using this result, prove regret bound of ([d/ayTTlog(BT representing significant improvement over prior works, all of which scale either exponentially with (8 > 0 or depend on the cardinality of the action set. To the best of our knowledge, this is the first regret bound for any logistic bandit algorithm that does not scale exponentially with / while remaining independent of the action set's cardinality. Finally, we present specific seltings where the dependence on a can be controlled. For instance, when the action space fully encompasses the parameter space, the regret Thompson Sampling scales as O(dTT). Overall, these results help explain the empirical performance of Thompson Sampling in logistic bandit problems across different logistic regimes and for large or contimuous action spaces, and highlight the importance of alignment between the action and parameter spaces.
which scales only logarithmically with B,
An exciting direction for future work is to extend our analysis to the broader class of generalized linear bandits. The properties the logistic function that we leverage in our analysis could be shared by other classes of link functions and could be used derive regret bounds using a similar analysis of the information ratio as we performed in Scction
Another interesting research direction is to use the result in this paper to derive regret bounds for logistic bandits in the frequentist setting. A promising way is to apply our information-theoreti analysis to the optimistic information directed sampling algorithm introduced by Neu et al. (2024). We believe that this approach could lead to new and improved frequentist bounds for logistic bandits.
13

---

Published in Transactions on Machine Learning Research (02/2026)
References
Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 176-184. PMLR, 2017. URL https: AISTATS 2017.
//proceedings. mlr, http:///........pppe//////////aa httppp////////aaallllaaaaaaaaaa/
Mare Abcille, Louis Faury, and Clément Calauzènes. Instance-wise minimax-optimal algorithms for logistic bandits. In Proceedings of The 24th International Conference on Artificial Intelligence and Stalistics, Proceedings of Machine Learning Research, pp. 3691-3699. PMLR, 2021. URL https://proceeddigga mlr. wwtppppssssvvveeeeeeee http:////aaaeeellaaaaaaaa html
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalilies: Nonasymplolic Theory of Independence. Oxford University Press, February 2013. doi: 10.1093 http://ccoffoso///70001010000
001.0001. URL https://acaaemicc www. cot.pccooooooo/o/66549999999999
Djallel Bounefoouf, Irina Rish, and Charu Aggarwal. Survey on applications of multi-armed and contextual bandits. In 2020 TEFE congress on evolutionary compulation (CRC), pp. 1-8. IEFE, 2020.
Stephen P. Boyd and Lieven Vandenberghe. Conver Optimization. Cambridge University Press, Cambridge, UK: New York, 2004. ISBN 978-0-521-83378-83
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Advances in Newral Information Processing Systems, pp. 2249 2257, 2011. URL httpp:///proceedings neurips.cc/paper/ 201 o011hhaa//6500077772227666666666 wtwp://aaaad.dddattatttttt...e
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic Linear Optimization under Bandit Feedback. volume 21st Annual Conference on Learning Theory, pp. 355 366, 2008. URL http:: /ttpp::/oppnalex... org/
W50486269
Shi Dong and Benjamin Van Roy. An tetrmmation-theoreti analysis for thomppon sampling with many actions. In Advances in Newral Information Processing Systems 31 (NeurIPS
2018), pp. 4161 4169, 2018. URL https: httpse//prroceednggs wwwprrisscc/ppperr//eeae 88hhash///hh//aa 185220006822112077cc551111633333 Abstrrtaattctt.tttcattt..c... Awstraatttttteee........e.taee.t html NeurIPS 2018; supersedes Xiv: 111418055..........
Shi Dong, Tengyu Ma, and Benjamin Van Roy. On the performance of thompson sampling on logistic bandits. In Proceedings of the 32nd Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 1158-1160, 2019. URL httpps://proceedingg.. mmr wttp.m..e.ee///////gggge/ee.ee/ html COLT 2019.
John C. Duchi. Lecture notes for statistics 311 electrical engineeringg 377: Information theory and statistios. https://weit stanfort ord. wdw.edd/lllll claaa///tatssllleettterenteeeee pdff 2019. Lecture notes; last. updated 2023-12-09; accessed 2025-09-10.
Louis Faury, Marc Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 3052-3060. PMLR, 2020. URL https://pproceeding.
mlr. wtt.ppees/v119/// w1t1///f////......mm html
Sarah Filippi, Olivier Cappé, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized lincar case. In Advances in Neural Information Processing Systems, 2010. URL htttps:/paaper..tt
Amaury Gouverneur, Borja Saariguuz-Gáálver Tobias Oechtering, and Mikael Skoglund. Thompson sam- pling regret bounds for contextual bandits with sub-gaussian rewards. In 2023 IEEE International Sympo- stum on Information Theory (ISIT), pp. 1306-1311. IEEE, 2023. doi: 1111109/SST54473.20000 10200692. TTt.:ttpee///rrrrrrr////////000
Taipei, Taiwan. Refereed; supersedes arXiv:2304.1388
14

---

Published in Transactions on Machine Learning Research (02/2026)
Amaury Gouverneur, Borja Rodriguez Gálvez, Tobias Occhtering, and Mikacl Skoglund. An information- theoretic analysis of thompson sampling with infinite action spaces. In TCASSP 2025 - IEFE In-
ternational Conference on Acoustics, Speech and Signal Processing (ICASSP), February 2025. doi:
C0.1109/ICASSP446660.22 202.0666022...822222222222222000
Robert M. Gray. Entropy and Information Theory First Edition, Corrected. Springer-Verlag, Information Systems Laboratory Electrical Engineering Department Stanford University, 2013.
Roger A. Horn and Charles R. Johnson. Matrir Analysis. Cambridge University Press, Cambridge; New York, 2nd edition, 2012. ISBN 978-0-521-63940-2.
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenly Third International Conference on Artificial Intelligence and Statistics, volume 108 Proceedings of Machine Learning Research, pp. 1066-2076 PMLR, 26-28 Aug 2020. URL html AISTATS 2020; replaces arXiv:1906.0994
https: h/tppe///prccedingss mlr. pwtps//v10//vvettoorreeeoo
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661 670, 2010.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. Tn Proceedings of the 34th International Conference on Machine Learning, pp. 2071-2080. PMLR, jul 2017. URL https://proceediing
mlr, ppwsss/v00/1117..tttn ICML 2017.
H. Brendan McMahan and Matthew Streeter. Open problem: Better bounds for online logistic regres- sion. Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pp. 44.1-44.3 PMLR, 2012. URL https://proceeddngs mlr press/v23/
mcmahan h
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Information-thooreta gencralization bounds for SGLD via data- In Advances in Newrul Information Processing Systems 32
Daniel M. Roy.
dependent estimates.
(NeurIPS
2019), pp. 11013-11023,
URL wowdddooo-orrr////aaaaaaaaaaaaaa
2019.
mips. hwtpppppprr.niisscccppppaaeeee
9282-informatt
NeurIPS 2019.
Gergely Neu, Inliia Olkhovskaia, Matteo Papini, and Ludovic Schwartz. Lifting the information ratio: An inforricio analysis of thompson sampling for contextual bandits. In Advances in Neural Infor- mation Processing Systems, volume 35, pp. 9486 9498, 2022. URL httpss:/prroceedinggg www.:eeeeddnnnnn.nnneeeeeeeeeeee nww.ipe...p.... cc/
paper paper_
html
Gergely Neu, Matteo Papini, and Ludovic Schwartz. Optimistic information directed sampling, In Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 Proceedings of Machine Learning Re- search, pp. 3970-4006. PMI.R, 2024. URT, h httppp/eddnnnn....pppee///////ee 2024; replaces arXiv:2402.15411
mlr. press//247/neu22422 html COLT
Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning- Cambridge University Press, Cambridge, 2025. ISBN 978-1108832908. URL httpp:://wwt wwwwridgeebbeeeeee Seabbridgg.or//hhggheeeeaass
First edition.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathemaaiccs of Operalions Research, (4):1221 1243, nov 2014. doi: 10.1287 10.1287/moor. /00.0.000......050... URL URL/ittts://ppussnnnnn inf informs.
org/ 1tt////111011111/0000000 2014.0650
Daniel Russo and Benjamin Van Roy. An information--hhorrticc analysis of thompson sampling. Journal of Machine Learning Research, 17(68):1-30, 2016. URL http:///wl...orrrappprs///////// html
Peer-reviewed journal version; supersedes arXiv: 103.5444
15

---

Published in Transactions on Machine Learning Research (02/2026)
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-dirreted sampll Operations Research, :6:00 252, feb 2018. doi: org/ org/doi/10 12w// 2017.1663
URL httpp::/pubboon/ ine. informs.
Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Tan Osband, and Zheng Wen. tutorial thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-96, jul 2018. doi: 10.1561/220000007
URL https: h httppp//w..............///////aa
William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the
evidence of two samples. Biomelrika, 25(3-4):285 294, dec 1933. doi: 00.1008/biomeet/25.--444 URL https://dbl..rg// 10. 10.1100///ooommt//553-4444
Ramon van Handel. Probability in high dimension. https://veb. math. princeton. cctu/-rvan/APC550 pdf 2016. APC 550 Lecture Notes, Princcton University. This version: December 21, 2016. Accessed 2025-09- 10.
16

---

Published in Transactions on Machine Learning Research (02/2026)
Appendix
The appendix is organized as follows:
Appendix
A
introduces four important lemmata for main results;
Appendix formalizes the proof for controlling the ratio of expected variances between the functions 3 and
8;
Appendix
C
extends our information ratio analysis to general action and parameter spaces;
Appendix D provides analysis of the functions 0g and As(55);
Appendix illustrates how translating directly linear bandits bounds to the logistic bandit setting leads to regret bounds scaling exponentially with 8;
Appendix elaborates on the gaps in the previous literature mentioned in Section |
Appendix G provides additional details the numerical experiments presented in Section
A Useful lemmata
Lemma 11 Let U be random variable taking values in [0,1] and Bern(U) be Bernoulli random variable with probability U. Then it holds that
I(U Bern(U)) 24(U).
Proof 20 Using Polyanskiy & Wu 2025 Theorem 3.4.d), we decompose the mutual information between U and Bern(U)
I(U: (U))(U)) h(Bern(U)) - h(Bern(U))U),
Following Duchi (2019 Example 2.2) notation, we define h2(p) = -plog(p) - (1 p) log(1 p) for p [0,
and rewrite the mutual information as
I(U: Bern(U)) = ho (E( E[h2
(3)
From Toylor expansion of (2) we have that hz(z) h2(p) (( ((--)))) for some & (0,
as h22 is continuous on the interval [0, 1]. We compute the second derivative of hr and get KT(E) = -
for & (0, 1). This function is concave and marimal at E 1/2, where takes the value h2(1/2) -4. We then have that for all [0, 1] and all p [0, 1],
h2(x)= & h2(p) (x p)h((p) 2(x -)p 2)
Using this fact for U and B[U], have that
UU) & h (E(]) + (U B(UT)NA(B(U)) 2(U 2
Applying the last inequality to the second term in eg- 3 it comes that
(U;Bern(U)) >
Finally, simplifying terms and taking the expectation gives the desired result.
Lemma 14 Let U, be random vectors in Rd and let Ú, V be independent random variables with distribu- lions equal respectively to the marginals of U. V, then it holds that
E E < d 17
17

---

Published in Transactions on Machine Learning Research (02/2026)
Proof 21 This useful fact is presented in Dong et ol. 2019 Lemma 16). We provide the full proof below.
Let Q = VVV II, then
B MV E[U Q12Q-11211 (
E (1000001000000000100000000000000
BIQQ "0000000000000000000000000011110 QIIIILEUUUUIIIU
B
(Tr(Q- -[V]E[]]] ) (Q (Q (/-
- (111)1((0111 + ( " B(V
Tr
(1 V (I Q
= -d-B((OTV)).
where (1) follows from the Keuchey-Schwary inequality applied to the inner product; (1) follows from the Cauchy-Schwarz inequality applied to the expectation; (k) follows from the identity that for any random vector W and deterministic matrir M, we have remainder of the proof follows by expanding the covariance Cov(V) [[[V]] [[V] rewriting the inner product as the trace of an outer product, and using the fact that the trace of a product of symmetric malrices is invoriant under cyclic permulations.
Tr(M, Cov(W)) E[ M. M.W. The
Lemma 15 Let f R4 R+ be such that f(0) > 0 and f(()/C is non-decreasee over Ç 2 O. Then, for any non-negotive random variable U, it holds that
[[((U)] BLU
V[((V]
VUU
Proof 22 This result is presented in Dong et al (2019 Lemma 18). We show that it can be obtained by combining Cauchy-Schwart inequality and Chebyshev's 's associalion inequalily.
Let g(C) = S(C)/C for Ç > O, and set g(0) = limęıo F(C)/C. By assumption, g is non-negative and non- decreasing. We have that
B( E
BLO(U)U ( Elo(U)UJBIU] EL((U) ( ELA(U) E[U
BUU()
ETU
B[U]
E
E
where (i) follows Cauchy- -Suucyy-Scwarz inequality [[XY]| & |E applied with X = ((U) and Y
VU; and (i) follows from Chebyshev's association inequality (Boucheron et al. 2013, Theorem 2.14). We then have that E[f(U)]E[[U3] & E[ Subtracting E[CTEE](()]] on both sides we get that
LEU -[ =[[(()) < E[UTV]](U)].
Finally rearranging the terms gives the desired result.
The following two lemmata are particularly useful to control the covering number in Euclidean balls and spheres.
Lemma 23 (van Handel (0016 Lemma 5.13)) Let Ba(0, 1) denote the d-dimensional closed Euclidean wnit ball. We have [BB,( 1), -I l12, for e > 1 and for 0 < s < 1, we have
d
& [WBB(0 1).1l 112,8) & 2 d
18

---

Published in Transactions on Machine Learning Research (02/2026)
Lemma 24
PPolyanskiy & Wu (2025 Corollary 27.4)) Let S₂(0, 1) denote the d-dimensional Eu-
clidean wnil sphere. We have ( (0, (0, 1),1 || (12.5) = for > and for e 1,, we have
1
10),l |12.=)] & 2d 1+ 1 d-1
2
B Bounding the ratio of expected variances over the functions As and A
Lemma 19 Let A5(x) = 0z(1) - os(1 - x) and ils surrogate Ag as in Defonition 16 Then, for all B > 0, it holds that
V B 1 (A, 16]
E
< 4.
E
V
A 1 - (A, |6]
We begin the proof by noting that the ratio of expected variances can be written as a ratio of expected squared differences,
(A, 4, |4 E B - (A, @T] (1 - 4, (À, 6)) (l(As(X) - [X))
& (A,
(l(As(x) - {x))
where Ô is random variable independent and identically distributed as O. We can write it in more compact form using X = 1 - (A, θ) and X = 1 (A,
We contimue by observing that for x e [0, dsl, we have Āg(x) As(x) = and for x [5g. 21, we have that A5(x)= - As(x) & As(6g)/6g(r: - 6g) as A5(ōg) & As()). Thus we can upper bound the difference
As(x) (x) by function Gz(z) such that
x [0,5g[
Gz(z)= = ((z (g)ossos(6))/6 IE [0g. 2].
We note that for all v, y [0, 2]. we have that
[ -z(z)- As(v) Gp(x)) (A)(2) -
- (Ao(v)).
Indeed, for x, e [0, 83], we have oac-aaaaaaaaeec-------------0---
- {s())) for v, E66g1.22
we have (xx) + Gz(z) As(y) - As(y) + A0(0g)/0g(z y) > A As(d)) +
Ag(5))/ōa(z y) ((4 -x)- As(u));
(:00:)))-Aaa00/((--666]]] (e, we have again (0)))))(()))+++ (0 6,)
and for =
[0,6g].
Ag(y)-
Ga(z)]
As the inequality (As(z) - -())) (Ag(z) As(v)) holds everywhere, it holds also in
expectation and we have that
(X)) - (x) (l(A((X) - 42(8)+++++++00))))))))))))) G
-
(X(A,(X) 4x()))
[[(As(X) - (x) -((x))))))()))
B[(Gg(X) - ()
1 2
([(As(X) (X))
B[(As(X)- - 2
B[(G,(X) 9
B[(G -[(G)(X)-G(())
< 31+2
(X(As(X) - -
(((As(X)-As(A))))
-
B[(Gs(X) -
(3))) -
1+ -11+
(4)
([(As(X) ())
19

---

Published in Transactions on Machine Learning Research (02/2026)
where in the second inequality, we used Cauchy-Schwarz inequality. We can then focus on studying the ratio of expected squared differences between Gg and Ag. We will first apply a transformation fs(x)
min( min(Ap(6g)) max max(A)(1)xz)) to crop the values of Ag that are above Ap(òg). We can write the resulting fanction fa o A3 as
(1(1)
x [0,1]
o Ap())
As(z)
x rg]1,
As(6a)
x [6,,
We observe that the transformation fa contracts the function As as, for all x. y E [0, 2], have |f A fo Ap(v) < (v()) As the inequality holds everywhere, it holds also in expectation and we have that [fs o fx
(x)x) and it follows that
Bl(Ga(X) - Cs(())
BX(Ga(X)- - Gs(X))
[[( B[(As(X)- (x) BI( Ax(X) - l/ {x))))
Switching back to the notation 1-(A, θ) and 1-(A, b) instead of X and X and letting p(0) denote the probability density of O we note that the above ratio can be equivalently written as:
1 (0..0, 02) [2 dog d0, dA, SSS0s E [fss A0 (), - fs A (A, ())) 6,0,0 (oo 0, 0z) 12 (P(,, doa di1 d0,
SS - Gz (1) Ó 0,
In the next part, we will bound the ratio between E[GG(L-(AA))--g1--AA (A) As(1-(A, ")) conditioned on é, {6u, 62], for any triplct f, 00.01,00 00,11,0, B2 E O, providing an upper bound on the above ratio. We denote this ratio R(Ø). Without loss of generality, we consider 0, 0g, O2 E O with associated conditional probability Pa, P1.P2 EJ0, 1], where po P1 P2
and E[(sa a
and 1- -0,, 02), 1 - (0,, 02). We introduce the notation A = 2popi (po + pı), B- = 2pop2 (Po + P2), C = 2pIP2(P1 + P2), and D = 2poP1P2. To upper bound the ratio of expectation conditioned on 0,0,0 θ E (0o. 02), we have four cases to consider:
we let
(0o, 01),
(i) (1) < 63. (0o, 62) 83. 1 02) = 89,
(ii) (fo, 01) > 53. (fo, 62) 53, 1 (01,02) & 6g,
(iii) - (0o, 01) > 6z. (0o, 02) > 5R, 1 - (2) & 6g
(iv) - O1) > dg. (0o: 02) > 5g. 1 - (0.,0>> > 83.
In the case (i) we have G1 (0m:: 0n)) fa A3 (0.. 0n)) for m.n (1,2,3) and the expectation
over Gg and fa Ag are equal. In the case
[ii
can write the ratio of conditional expectations
(A 2D) ()))))(())))))) 5z)2
ADo(0a)² + BA2 CAs(c)) D(As(6g) - (b)))) + D(As(ds) - Ao(c)) +D(A()) Ag(c))2
We note that the numerator N(a) is maximized for a = 2, where it takes the value N(2) As(6s)²
(A +
oj
22) - 8)2 and that the denominator D(b,e) is minimized either by b= c 0 if D < B or D < C, with
D(0,0) 0) =
For b = c c= 53 to be a minimizer of D(b, c) we would need to have simultancously
B < D and C < D, implying that > 1/2 and Po > 1/2, which is not possible as Po + pt < 1. So the maximal ratio is ((2) ((,00) 0) which equal to (2-
In the case
iii
we can write the ratio of conditional expectations as:
(A=(6))60a) (A+))))))((( D)(b dz) + D(a- - b)2) As(c))²
AA (6,)²
20

---

Published in Transactions on Machine Learning Research (02/2026)
We can verify that the numerator (a. is strictly convex and quadratic in a, as its Hessian is positive- definite. We can compute the Hessian by taking second partial derivatives:
8 b(, Oa²
Na, b) 062
Na,
2² 2², -2D.
2A + 2D,
2B
2D,
δa
δbōa
(2A+2D 2D
2D
We then obtain the Hessian as HN
which is symmetric, and strictly diagonally dominant since both diagonal entries are strictly greater than the sum of the absolute values of the off- diagonal terms:
-2D
2B 2D
2A + 2D > 2D,
+ > 2D,
which holds as A, B 0. Therefore, by Horn Johnson 2012 Theorem 6.1.10), the Hessian is positive- definite, and thus ((a,b) is strictly convex. Since N(a b) is strictly convex on the compact convex set [6,, 2] [6g, 2], it atlains its maximum at one of the extreme points of the domain. These extreme points are
b) { (2, (2,5g) (6g, 2), (53,
We have that ((63, 0.3) = 0 and for the other corners, we evaluate
N(2, 53) = (A + 2D) A (6)))
(d(a))
(2 - -5)) N(ō,, 2) - (B 2D)
(2 -8
83
(
22, = (A+ B + 2D)
(2 - -
83
thus the numerator N(a, b) is smaller than N(2,2) As()a) 8g) + B 2D). Looking the denominator D(c) = (A+ ())) ( +2) we note that it is minimized by c = 0 if C 2D and takes the value D(0) = (A+B+2D) and the ratio N(2, D(0)) (2-6a)²
o3
8
Lastly, we need to consider the case fiv)
where the ratio of conditional expectations can written as
A(a - 6,) + B(b 6,)² + C(c D(a b)2 + D(a - c)² D(b - c)
0 (A+ B
We define N(a, b, c) as the numerator, and compute the Hessian by taking second partial derivatives:
2
2ºN 2B 4D,
2ºN Oc
G caōb
2º 22N
24 + 4D,
2C 4D,
-2D.
da
2
Ōaδc
abcc
The resulting Hessian is:
2A + 4D
-2D
-2D
HN
-2D
2B 4D
2D
-2D
-2D
2C + 4D
This matrix is symmetric and strictly diagonally dominant since all diagonal entries are strictly greater than the sum the absolute values of the off-diagonal entries:
2A + 4D > 4D, 2B+4D>40
2C+4D> 4D,
which holds since A, B,B.C. C > 0. Therefore the Hessian is posilive-definile, and thus N(a, b, e) strictly convex. The domain a, c E [őg. 2] restricted as the sum of the angles between the vectors 6,, 01, O2 is at most 2n (the maximum is achieved when lg 0 0g are coplanar). We can express this condition arccos(1-o)) arccos(1 b) + arccos(
& 2n with a, 1 b, ce [63 1, 1]. The function arccos(2) is concave for [0, 1], and the sum of concave functions is concave, so arccos - a) arccos(1 -b) arccos( cc))
21

---

Published in Transactions on Machine Learning Research (02/2026)
is concave. Then the superlevel set arccos(1 a) + arccos(1 b) arccos(1 - c) < 2n is convex, see Boyd & Vandenberghe/ [2004] Section 3.1.6).
As the function ((,,bc) is convex and the domain a, 6, C [ōg. 2] subject to arccos(1 - a) + arccos - b) + arccos (1 - c) & 2T is a convex set, it is maximized at points on the border of the domain. At the point a c 6g, we have N(63, 5g, 63) = O. As a, a,b,e 3 óØ > 1 (see Appendix D), it implies that arccos(1 - a), arccos(1 - b), arccos(1-c) c) E] T], thus the condition arccos(1- a) arccos b) arccos(1-o) c) & 2 implies that no point a, b, e can reach 2. The remaining extreme point is therefore when two points equal to óg and the last one is such that arccos(1 (oo((1aa) a) arccos - b) arccos - c) 2T. We can assume without loss of generality that A > B and A > C' and to simplify the exposition, we let 0g = arccos(1 - 63). The maximum of ((, b, c) is given by [[t, V4, 63) where t is such that arccos(1 - 1) = 2x - -20g. We have that = 2- 100122((6)))) 6g)² 26 (2g)) Thus we have that (it,, 6z) (A + 2t 5z)² (A+ (A+2D) (26 (2 5g) - -dg)² (A+ 2D)6 (3 26g)² & (A+2D) 5n)².
= 1 cos( 2n - 22 = 1 cos(20g) = 1 (2 (00)
We then use the fact that 2D B + C' for all po: PI. Pa E [0, 1] to conclude that
N(a,b,
(A + 2D) 22 6z)²
(2 -53
+ C+
63
From the analysis of
i
i
iii
and
iv
we conclude that, for any O, 02 0g E O, we have
B[ ( - Gp(1 - (A, | 6,0,0e (0,,01 023]
(2 - 8p)²
B[ o Ap (1 - fa p (1- ( 16,,00 ( (0o, 0, 02]]
82
and therefore, it holds that
(2 8g)²
E (Jo (1-11 (A 6))
Using the above result in Equation
4 we get that
E
V
A
1 - (A, 0))
6
2 - 6,
2
[+
83 4.
E
Ag
1 (A, θ)
6
where we used that 8g E [1,3 (see Appendix D for a detailed proof).
C Extension to general spaces
To extend the proof technique of Section 5.2 and Section 5.3 we first need to introduce the alignment function (0))= := (0))) as well as optimal environment mapping p(θ) arg (O.)), 0) We can define the eztended regret function (3 == (a os(a- - r) and note that
As(a(²) (A, (()) ())(((())
()<((,)))
Integrating over the Bernoulli outcome, we can write the expected regret using
B[As(a(0) - (A, 0) a()))
E E[os((A' (()) θ))]
where we used that é and are identically distributed and that the inequality (T. p(0) > (T. (0)
holds point-wise for all 0 e O and therefore holds expectation. Similarly to the proof in Scction 5.2 we construct a function Ag(z, (()) as the tightest upper bound on As(z, a(²) that satisfies the requirements
of Lemma 15
22

---

Published in Transactions on Machine Learning Research (02/2026)
Definition 25 (Extended regret surrogate) For every 0 O, construct the extended regret sur- rogate function As(2, a(0) as the tightest upper bound on Ag(z,a(0)) such that A a(0))/a is non- decreasing over 2 O.
Namely, let (3(a(())= = arg ma Ar(z,a(01) we define the function As(a, a(0) as
a()))
x 10, (0,8)(((0))
as(z,a(0))
As(os(a(0)),a(0) + (z - -=(((())) kz(a(())
*E [
where nz(a(()) = 4p(5)(a(0)) = max =a0.5(00++a000) a
We are now equipped to extend Lemma 17 to general action and parameter spaces.
Lemma 26 Let the extended regret surrggate be defined as in Definition 25
Then, holds that
[[Bern(ds((AA, ())) Berr(os (A & 2d E v -Ad,))))((A)))))))) a a(²))
- (A,
61]
Proof 27 The proof follows closely the technique used to prove Lemma 17 We note that conditioned
θ 0. the exlended regret surrogale is mapping from [0, 1 a(0) to [0, IJ, that A,(0, al)) ()(a(())-
(s(a(())- and fulfills the assumptions of Lemma 15
Noting that V (T +)) 6) =
|6] and using Lemma 12. we have that the
information ratio I' can be bounded by
E
A
(((0) (A,) +
T d
E
A (a(0) (A.) θ
Similarly to the analysis for the case O s A, we continue the proof by noting that the ratio of expected variance can be written ratio of expected squared difference,
E
As(a(²) (A, (A, 0). 6
E
(A) a(0) As(a()) (( " é -A
E
As(a(E) (A, (),)), 6
E
E
E E
E
E
- -
where Ô random variable independent and identically distributed as θ and in the last equality we used more compact notation X a(() (Å,e) and X a(θ) - (A.
Conditioned on ê = 0, for e (3 @T we have Ás(x, have that Ag( a()) & As(r, a()) (z)) - )z(a(())) as (s())(a(0)) a()) & As(x, an Using this observation can upper bound the difference - by function Gs(a, (0)) such that
a and for x [ō)(a 27, we
0 - (( (0
Gs(s,a(0)) -
==(0)(o(0).22
We note that for all x, y [0,2], we have that
As(z, (()) Gplz, (()) As(y, Go(y, (s(z, Ac(i,a(0)))
23

---

Published in Transactions on Machine Learning Research (02/2026)
Indeed, for y. [0,b)(a(0)], we have (z a(0) + (2(2,,(()) As(y,a(0)) Gs(v,a(0)) and (s(x,a(0)) - As(y. a())) are equal zero. Then for z, y E (6z(a(0)) 2], we have that
As(z,a(0)) + G3(Z, a (0) - As(y, - Galy, a()) = [2 a a()) - Asl,, a()) + +n)(a(0))(( y) Az a(0) as(y.
and for ze (ds(a(0)) 21, v (0,))(((f)),, we have again
(As(2, -bt GGp)
(0d > (())- a()))
As the inequality a())), + Gz(2,a(0)) (()) Gg()) is greater than or equal (5((z,a(0) As(y, holds everywhere, it holds also in expectation, and we have that
- 3 a())))
((()s(X,a(0)) - A3 - (I a())) 1
-
El /tt.a///ao.aaaaaaa.aaaaaaaaaaaaa
1+2
El [(A4)(X.(()))
(())
(X (()) G CO( (X(A - As (())) El(As(X, - As(x
1+2
(5)
where in the second inequality, we used Cauchy-Schwarz inequality. We can then focus on studying the ratio of expected squared differences between G3 and Ag. We will first apply a transformation f(x) - min(As (5)((((())) a(0),, to crop the values of Ag that are above As(0s(a(0)),a(0) We can write the resulting function f Ag as
(oAs(e,a(0)) = As(z,
x (=(00))(a(0)
As(ōg(a(0)), a()) ==(6)(a(0)).{
We observe that the transformation f contracts the function Ag as, for all r, E [0,2], we have If As(x, - f As(v, & [ a(0)) As(y, a())). As the incquality holds every- where, it holds also in expectation and we have that E[(f o a())-= a As(X, & ((())(X,a(0))-AA{ (())) and it follows that
B[ a ( Gg(X, & [ al 6)) - (x(() (
((() Gg [I(S (x (()) - As (
Similarly Lemma 19 we will bound the ratio conditioned on é, θ (0o, 02}, for any triplet 0o, 0,, 02 e O, in order to provide upper bound on the ratio when taking the expectations over Oo 01, Og O.
Using very similar proof to the one for Lemma 19 we can show that
E [ ( 6,0,0 (0o.01 02.11
4k (1=a)))(+=
B[( e Ax fo A (X, a é, 0, (0o. 01, 02}]
Ap(ōs(a).a)²
where a minjeo (4)) & 1. Then using the definitions of kạ(a) and As(a, we can simplify the right-
hand side of the above inequality as
4(1 11+a--00 )g(a))2 a(gaa))(a))²
(4 (8)
An(ō)(a),a)²
83(a)²
83(0)²
24

---

Published in Transactions on Machine Learning Research (02/2026)
Plugging the above result in Equation
get that
E V A (a(²) (), 0) (9,,)) 6 6
(1+
4 - --28((a)
2
42
42
<
1+
& a²
E A (a(6) ((66)-(44 (Á. 6) 6
65(()
óg(a)²
where we used the fact that (3(() 20 a (see Remark 28 This result concludes the proof of Proposition
Remark 28 Remark about a & )ạ(a) for all a E [0,
We recall that Ag(a, a) (5(()) (a - x) and start by computing the derivative of As(x,u)/a:
dr (Asle,a)) d/z(a- 2) (òg(a) - Φs(a- - =x))
d
x²
Let Nxx, a) be the numeralor of the above ratio, the firsl-order condition for the mazimizer can therefore be written as
N a) = x2(a) 03 - -x)
-x x) x's'(aa =x),
== and the equality N(x,a) 0 achieved for x = 55(a). We observe that N(0, a) = -g(a) = We
will now show that ((x,a) is strially decrensing for x [0.a] (thus (sr,a) < for x e)0,a)) and strietly increasing for x z a, which implies that the equation ( has a unique positive solution and that this solution is strictly larger than a.
To do this, we study the sign of d/deN(x, - < x) for x [0.a] and for x. i As x 3 0 is always non-negative, the sign of the derivative is given by the sign of Sziaa =x). We recall that (² = 5 so)g(2)(1 (1(=))(1- 10:11-20g0 20z(2)). As 0s(2)) E [0, for all 2 E R, we have that d'z(2) is positive if d5(()) < 1/2 and negative if (z(2) > 1/2. As (s(() = 1/2 and (b)(2) is increasing, we have that (bs(z) < 1/2 for all < 0 and (s(z) > 1/2 for all = 0. Therefore, for x E 10, a], we have that - x 2 0 and V2 x) < 0, which implies that N(x, a) is striclly decreasing for x E [0, Similarly, for x 2 a, we have that a x & 0 and o (a x) > 0, which implies that N(x,0) is strictly increasing for x 2 a.
Analyzing the functions As(dg) and 53
In this section, we study the quantities (005)/65 and 83, illustrated respectively on Figure and Figure We will prove several important properties of d,s (6 which are used in the proof Lemna 19 First,
we prove that the function <z(x) == Ag(æ)/2 has a unique maximizer 6g which lies in between ]1, 2 Then prove that dg is decreasing function of B. We then analyze its limits and show that lim d, 3/2
and limz-wz6--1, thus refining the domain of 8g to [1,3/2]. After that we analyze the monotonicity of the function (6 and show that it is increasing function of 3.
D.1 Uniqueness of the maximizer 5,3
To see rigorously that kz(z) has exactly one maximum in [0, 2] and that this unique maximum 63 lies in the interval [1, we will follow a similar technique as in Remark 28 that is studying the derivative of kz(2)) to derive optimality conditions and showing that these conditions are satisfied by only one point in [1,2]. We start by computing the derivative of kz(x):
k¹((z)= (Ar(²) y d/1(1 - (((1-))x (00(11) d -xxx x))
x²
20 where we used that (x = d'y(1 x)) and 40(x)= - z).
Let N(x) = dy(1 x)ι 01 x) (1) be the numerator of n²g (z). Since the denominator x² is strictly positive for all 0, the sign of (1) determined by the sign of N(x) and the sign of N(x:) has to reverse
25

---

Published in Transactions on Machine Learning Research (02/2026)
1.5
69
As(5g)/63
8 10
8 25
0.8
8 6
0.6
0.4
0.5
0.2
0
0
0.5
1
1.5
2
0
20
40
60
80
100
3
Figure 4: Illustration of (x) As(r)/x over
Figure 5: Illustration of 63 and (6 as func- lions of B. One can observe that dg decreases with B while As(65)/8g increases.
x E [0, 2] for different values of 3. The maximum of the function is attained x =3.
the maximizer 53. We will start by studying the derivative N'(x) = =x====d((1-1)) z)) As x =100, 2] is positive, the sign of (x) follows that of - (1 - x) = - - x1 - 60 x))(1 1011-200 26 - x)), and we have and negative when 0s(1-x)
1/2, that is for 1. We therefore have that [(x) is increasing over the interval [0, 1[, reaches a maximum x and decreases over the interval 11, We now evaluate (xx) the points
that (x)x) is positive when Φ (1 - r) < 1/2, that is for
0, 1, 2. We have that (0) (1) (x( and (1) (0)()) + +0)) (()0))(((1))) (1) 8/4 1/24+1/2-0001/ 0d((). Now let f(8) o3()), we have that = 1/2 + 8/4, therefore we have that ((1) > 0 for 8 > 0. As NN 0, N(1) > 0 and N'(x) > 0 for e [0, 1]. we have that ((x) is positive over the interval [0, 1]. As Nx()) is negative for x 2,, by continuity of the function, we only have to show that N(2) < 0 to prove that there exists a point 63 in [1, 2] at which N(x) changes sign. We have that N(2) 26g((1)
(()) is maximal for 8 = and for 8 > O, we have that S(3) < f(0) + 8'
Φs(() and we have that N(2) (1)(( (1)) -1)26)));)))))) As (1 [1/2, l. have that d1) (s)) 1/4 and therefore N(2) & B/2 + 1- 26g(1) 2(8/4 1/2 ds(1)) < 0, using the same argument previously. As N(x) is positive over [0, IJ. strictly decreasing over ]1,2]. and negative at x = 2, there exists a unique point 8g E [1,2] such that N(,g) = O. We therefore have that Kg(x) has a unique maximum ōg in [1.
(5(-1) (1). Then using that ( 1)
that (-1) = (
D.2 On the monotonicity of 6g
We now study how the quantity & varies with To this end, we analyze the total derivative of the first-order
optimality condition satisfied by dg, which takes the form N(x,3) = d's(1 x)œ Φs(1 - x) dss().
Since 6g is defined by the condition ( Ø) O, may differentiate this identity with respect to 8 and apply the chain rule. We obtain
d5g + 0gN(53. 9) implying that dō, 0gN((5,, B) d3 0..N(5,.
0
d3 N(55. (6,(6,,))) -
d3
We now compute the partial derivatives appearing in the above expression. Using the identity d/((x) 30g(z)(1 (z(z)) and the chain rule, obtain Nz, 3) x10 z), where the second derivative of de given by (x(x)) 8 (z) ds(x)) 20g(z)). Since dg 1, follows that Φs 1111-60 -83) < 1/2, and therefore 1 21 53) 0. This implies that d% 6z) 0, and hence 0,N(6,, 0.
26

---

Published in Transactions on Machine Learning Research (02/2026)
We now compute the partial derivative with respect to 3 and we obtain
2gN(2, 3) = 2000 x) 0z00(1 - z) - مg)
where 02))(22) ds(x) - ))(+)) (1 + 3x(1 (x]( and 0z0g(2)-
(1(()))111ppam)) Substituting
these expressions into the formula for 03 (zr and simplifying gives
( 9) = 00((1 - 63)(1 - 55 61 + 36 - -8) 20 - -b1))
(s()).
We now let q 05(1 أو) and p (1( and plug 63 into the expression. Noting that (z0p(() ( ) we obtain 2 B) = q(1 - q) B5g(1 61) - 24)) p(1 p). We then recall that the first-order condition Nd 8) 0 implies the identity q 35 - q), which we may use to eliminate and simplify the expression for (g,V(63, A short algebraic manipulation gives
05,((63, 30 4) (3q(1-
-) 9) (1 -1-22 (1-24)).
The first part of the expression (1 is positive. We then have to analyze the sign of 8q ()(1-) 24) Since 63 > 1, we have that q < 1/2, and follows that 2q > 0. Furthermore, from the identity p-q= 36 9) and the fact that p < 1, we have 56 9) < 1 q 1-1120 2q. As 53 > 1, the incquality 8q(1 - 9) < 2q follows. We conclude that $q(1- 9) (1 2q) is negative, and so 0gN(68,,3) 3) <
Combined with the fact that (5,( 3) < O, obtain
dō 2aN(65, 9)
d3 (d < 0,
which shows that the value of óg is strictly decreasing with increasing values of B.
D.3 Evaluating 6g at the limits B - 0+ and B - oc
We now turn to the analysis of the limits of ó3 as 3 - 0+ and B - Jo. We begin with the small B regime, For small B, we use Taylor expansions around B = 0 and obtain
1 fx
(Bx)3
3
882² O(33).
xх(x)
O(33),
and
6's(2)
2
48
4 16
We plug these expansions into the first-order condition N(x,, B) = 0 and obtain,
833
N B)
1² 2z) + 0(35).
48
Dividing by 8 and taking the limit as - 0 shows that 03 must satisfy x²(33 2x) 0. The only solution
to this equation in the interval [I,2] is 3/2, and so conclude that lim 8g 3. We now analyze the limit B - s. Suppose by contradiction that there exists > 0 and a sequence on - 00 such that da 2 1 ++ e for all n. Then, since do. (1 ōg..) & to cc. But from the first-order condition
it follows that Φe. (1 8p..) - 0 as Bn tends
ds(1) 6s( - 53)
the left-hand side tends to while the right-hand side tends to O, which is a contradiction. Hence, we must have
lim dg 1. 8-300
Combined with the monotonicity of óg in 8, we refine its domain to 8g [[1,3/2] for all 0. These results are in agreement with the numerical results illustrated in Figure
27

---

Published in Transactions on Machine Learning Research (02/2026)
E
Adapting information ratio bounds from linear to logistic bandits
This section presents how to rigorously adapt the TS information bound from Dong al. (2019 Proposition 17) to the one-step compressed Thompson Sampling such that it can be combined with the regret bound from Dong & Van Roy 2018
Theorem 1) with Gouverneur et al. 2025 Theorem 1).
Proposition 29 (Dong et al. (2019 Proposition 17) extended to one-step compressed TS) For all B > O, under the logistic bandit setting with logistic function Φ5(x), letting O and θ, satisfy the conditions in Dong & Van Roy (2018, Proposition 2), the one-step compressed TS information ratio is bounded as
T();,0,) (e[R(,,(;;)) 0) R(T, ()),0) 9)] [( R(T,((,), θ) 6,)
(1 exp(
32 32cx
Proof 30 We combine the proof techniques from Dong et al. 2019 Proposition 17) and Dong Van Roy (2018, Proposition 3). To simplify the exposition we will omit the subscript and reuse the notation intro- With these notation, the one-step compressed information ratio can be written
duced in Section 3
[[Ber((o(((..f θ))) - (T., 0))1?
I(Ô*; Bern 00 (T. (+), 9))
Similorly to Dong et al. (2019, Proposition 17), we let L1 = inf (os(x)) = B (xp(())
(I+)xp(3)) and Le =
sup [a(=)"] = J. We will start by analyzing the numerotor which we write as
(
0>)) = EToo( (0), - (T( 0))1
(T.))
$ レ3 TT, (0)), +) (T.
(T. θi|²
where the inequality follows from dd(o1)) & sup [0s(2))| for all æı 22 E [-1,1].
We then focus on the denominator, which we lower bound similarly as in Dong & Von Roy 2018 2). Introducing the notation R(0) (ern(os((T.())) θ))), we write
Lemma
I(Ō"; (T ()), ②) I()):) I(O;; ())))))
Σ p P manj (()))
ieo, eteo.
Σ 110 -
θEC. P*EO.
where O. the set of values for the random variahles 9- and Ô, as defined in Dong & Van Roy 2018 Proposition 2). The inequality (i) follows from the chain-rule; (i) follows from θ and O being independent they satisfy the conditions in Dong 8 Van Roy 2018 Proposition 2); (k) is obtoined using the Donsker-
Varadhan inequality (Gray 2013 Theorem 5.2.1 as in Russo 8 Van Roy 2016 Lemma 3). We then continue to lower bound
(=) 2 Σ (600000@0--01(((((((((0)0) (T) O))))
deO, t.E0 > 2
tEO, Ō+eo.
using the fact that - 21 82
x inf - [ for all æ1, 22 e [-1,1].
28

---

Published in Transactions on Machine Learning Research (02/2026)
Combining the inequolity on the numerator and the denominator, get that
L3 T( 6,) & 2 Eioo (1--0)966--001100000000)00---0-0
(6)
()),
Without loss of generality, we write O. ( where for each i,j E (1,-..,|Oo]] the correspording entry is given by
0..13 Now, we define the random matris M E 00
Ma.j = v / - (0)) (O..
We note that we con rewrite eq.
6
using the trace and the Frobenius norm of the matriz M, as
L Trace (M)
L3
r(O; O2) & 2L3
&
Rank(M),
||
2L3
where the last inequality is obtained from Russo Van Roy
2016
Fact 10).
The proof concludes showing the rank of the matria M upper bounded by d. For the soke of brevily, we define Ô [[ and Qs == =[0]0-=01]] for all i {I.....|OII: We then have (T. ()(rr))) (T, (o,) Qi> and (0,), (T. (0,), O) Since the inner product is linear,
reurite each entry
Mi of the matrix M as
( -).
Equivalently, the malria M can be wrillen as
p(e - -
0P θ) V000000..10000000000
Pl 00, 1T (0s)
This rewriting highlights that M can be written as the product of a 10el by d matric and a d by 10 matrix and therefore has a rank lower or equal than min(d, (..l).
F Regarding the gaps in previous literature
In Section I we mentioned that the main results of Dong et al. (0199) are incorrect due to two issues. First, their regret analysis combines results whose hypotheses are not compatible. Second, their analysis of the Thompson Sampling information ratio contains an unaddressed gap for B > 2. We elaborate on both points below.
F.1 Regarding the incompatible results
Short explanation. The regret bounds in Dong et al. 20019 Theorems and 5) combine two results with incompatible hypotheses. Specifically, the paper uses a uniform bound on the information ratio of Thompson Sampling (reported in Dong et al. (2019 Appendix B, Eq. (18))) together with [Dog & Van Roy (2018) Theorem 1), which requires uniform bound on the information ratio of one-step compressed Thompson Sampling. Since bound the Thompson Sampling information ratio does not, in general, imply bound on the one-step compressed Thompson Sampling information ratio, the hypotheses needed to invoke Dong & Van Roy (2018) Theorem 1) are not satisfied by the argument in Dong et al. (2019). This mismatch is effectively introduced in Dong et al. (2019 Proposition 9), which incorrectly restates Dong & Van Roy (2018 Theorem 4), replacing the assumption required by [ong Van Roy (2018) Thcorem 4) (a uniform bound on the one-step compressed information ratio) by an assumption on the ordinary Thompson Sampling information ratio.
29

---

Published in Transactions on Machine Learning Research (02/2026)
Detailed explanation. In their analysis of Thompson Sampling for bandit problems, Russo & Van Roy (2016) introduced the information rulão, defined as the ratio between the squared conditional expected instantaneous regret and a measure of information gained from the observed reward. In the original work, as well as in Dong et al. (2019). the information ratio of Thompson Sampling is defined as the random variable
E2 [. R(A,, T,(A"; R0 ,), A,)
Te
where A, TT is the action played by Thompson Sampling and R(A,, Q) is the associated random reward.
Russo and Van Roy use this concept to derive general regret bounds of the form v (TTH(A*) under an assumption that the information ratio is uniformly controlled (e.g., [[[r]] & I for all t). This result is restated in Dong & Van Roy (2018 Proposition 1) using variant of the information ratio defined in terms of ④ rather than A".
Dong & Van Roy (2018, Proposition 1) For any time horizon T, the regret of Thompson Sampling is bounded as
[[Regret(T)) < -T-TTTTT.... H(O),
where is a uniform upper bound on the information ratio T2 0,) == [1 ,,,,,0,
A limitation of this approach is that H(A") (and similarly H())) can grow arbitrarily large with the number of actions, or be infinite when the action space is infinite or continuous. The work of Dong & Van Roy (2018) focusses on addressing this limitation. At a high level, their idea is to relate the regret of Thompson Sampling to the regret of an approximation they refer to as one-step compressed Thompson Sampling. Under continuity assumptions on the expected reward with respect to the action space, they derive bounds in terms of compressed statistic O2 of the parameter θ together with the information ralio of one-step compressed Thompson Sampling, defined as
r,; 6.) = E, E.[ (())) 6)]
(8)
Te (+;; ((., 0.)
Here , and θ, are auxiliary random variables constructed from θ and from a statistic θe, derived from the Thompson Sampling sampled parameters O,; see Dong & Van Roy 2018 Proposition 2). The resulting bound, presented in Dong & Van Roy 2018 Theorem 1), is of the form eT + (VTTT((.)) where e controls the quantization level and I' is uniform upper bound on the one-step compressed information ratio [,;0; 6,)
Dong & Van Roy 20018 Theorem 1) For any time horizon T, the regrel of Thompson Sampling is bounded as
[[Regret([]] E vf- H(O.),
where I' is uniform upper bound on i,(0;;,) 6,) and θ; and 6, are defined as in Dong & Van Roy 20118 Proposition 2).
Tt is worth emphasizing that the proof of Dong & Van Roy 20188 Theorem 1), via Dong Van Roy (2018) Proposition 2), establishes the existence of Oj and θ, but does not provide an explicit construction. Consequently, bounding I (,;; θ,) outside of specific settings (such as linear bandits) can be technically challenging. In the d-dimensional logistic bandit setting, Dong and Van Roy conjecture that rr(O;; θ,) is uniformly bounded by d/2; see Dong & Van Roy 2018 Conjecture 1).
Dong & Van Roy 2018
Conjecture 1) Under the logistic bandit setting with logistic function dg(x),
let O and O, be defined as in Dong & Van Roy
2018 Proposition 2). Then, for any B3 > 0,
d
T, 0.) < "²'
30

---

Published in Transactions on Machine Learning Research (02/2026)
Combining this conjecture with Dong & Van Roy 2018 Theorem 1) yields Dong & Van Roy 20188 Theo- rem 4).
Dong & Van Roy (2018) Theorem 4) For any 8 > O, and for all A, = Ba(0, with märimar
alignmmet conslant a > O, under the logistic bandit setting with logistic function Φg(2), assuming that the one-step compressed information ratio ['((rr, Q.) is uniformly bounded by I' (with I' = d/2 according to Dong
e Van Roy (2018, Conjecture 1)), the Thompson Sampling regret is bounded as
6V E R(eggrct & 2 2T 3+
Beas (1+
d
To apply Dong & Van Roy 2018 Theorem 4), one must establish a uniform bound on the one-step compressed information ratio T2(6; 6t). However, Dong et al. (2019) Proposition 9) instead assumes uniform bound the ordinary Thompson Sampling information ratio Pr..
Dong et al. (0019 Proposition 9) For any B > O, and for all A, = Ba(0,1) with minimaz aligroment constant a >> O, under the logistic bandit setting with logistic function (z(x), assuming that the information ratio of Thompson Sampling re is uniformly bounded by r, then the Thompson Sampling regret is bounded as
6v 2T
Bea8
[[Regret(T)] & 2 2 log 3+
d (1 + 6393
As written, Dong et al. the latter requires a uniform bound on [,; θ.), not on r,, Since T, and To are distinct quantitics, a uniform bound on H, does not, in general, imply uniform bound on H, without additional assumptions. This discrepancy undermines the derivation of Dong al. (2019 Theorem 5) and its corollary Dong et al. (2019 Theorem 1).
2019
Proposition 9) is not a valid restatement of Dong & Van Roy (2018) Theorem 4):
Finally, note that one can apply Dong & Van Roy of the ordinary Thompson Sampling information ratio. However, this route yields bounds that scale with H(O) (or H()")), which can be prohibitively large or infinite for large, continuous, or otherwise unstructured spaces. For instance, combining Dong & Van Roy (2018) Proposition 1) with our bound on the Thompson Sampling information ratio in Proposition 4 results in a regret bound of order log(())))) which becomes vacuous for infinite or continuous parameter spaces.
2018 Proposition 1) directly if one has uniform control
F.2 Regarding a gap the analysis of the information ratio Dong al. (2019)
We also identified an issue in the proof of Dong et al. (2019 Theorem 5) (end of the proof on page 20), where the inequality x > { 0.1A is stated without justification. This inequality used to conclude
bound the Thompson Sampling information ratio, but the only evidence provided is Dong et al. (001
Figure 3), which plots x(A, 3) and {(A, B) for the specific case / = 2. While the plot is suggestive for 3 2 it does not establish the inequality for the range required by the proof (in particular 3 > 2), nor does it provide a general argument. Moreover, the computation of x(A, 3) and {(A, 3) is nontrivial; we attempted to reproduce Dong et al. (2019 Figure 3) computationally and were unable to do so. Consequently, in the absence of a proof of X > {> 0.1A for the relevant regime of 3, the argument Icading to Dong al. (2019) (18)), and in particular the step used to control the information ratio for large B, is justified written.
31

---

Published in Transactions on Machine Learning Research (02/2026)
G Details on the Numerical Experiments
This appendix provides additional details on the numerical experiments presented in Section 6
To recall, we consider a synthetic logistic bandit with dimension d, horizon T, and logistic slope parameter f > O. We the d-dimensional unit sphere Sa 1) as both the action space A and parameter space O, together with a uniform prior on the parameter ② We approximate the expected regret using a Monte Carlo method and performed the posterior sampling of the parameter using the Metropolis Hastings algorithm.
We provide below details regarding:
the approximation of the expected regret using Monte Carlo method;
the sampling of the posterior distribution using the Hetssno algorithm;
the parameters we used for the simulations;
the accuracy of our approximation.
G.1 Monte Carlo approximation of axpected regret
To approximate the expected regret of Thompson Sampling, we perform K independent experiments of horizon T. At the start of each experiment & I....,K K draw 0% P(O). Then, for each time step {= = L, T, sample N parameters ( P(O)/I h&)) from the posterior, where hy denotes the history to time t. These samples are used to approximate the conditional instantaneous regret:
E R(T. 0) R(., H' n/.
(8..,) R(T. (0).,e)) (,,,,)) Σ
N
where M(a,) the expected reward for action a and parameter 0, that is R(a, E 0)). We then arbitrarly set 0x, = dI and sample a Bernoulli reward Tk, ~ Bern(on((@u., 02)) which we use to construct 1+t1 = h4 0x.r)
Averaging across experiments yields an unbiased Monte Carlo estimate of the expected regret at time I,...,T, effectively taking the expectation over the history of observations. The approximation of the cumulative expected regret up time T is then obtained by taking the sum over the time steps 1, 1,..., T:
T
K
N
E[Regrt (T)]
(O.x.))) ((m.(0g.k.))00a..
KN2
G.2 Posterior Sampling via Metropolis Masting
Since the logistic likelihood does not admit closed-form posterior, use Metropolis Hastings sampler with von Mises Fisher random-walk proposals on the unit sphere. The proposal distribution is centered at the current state with concentration parameter k, which we tune to obtain an acceptance rate of about 40%. The acceptance probability reduces to the Metropolis ratio
a(0 - 8') min (1.
1, L(0%: M.)
L(0 h()
where L(0; h() is the logistic likelihood given the history 14. At cach round, we run n iterations generate posterior samples.
G.3 Parameter choices
The parameters used in the numerical experiments are summarized in Table 2 The experiments were run NVIDIA RTX 4000 Ada GPU and completed in about 30 minutes.
32

---

Published in Transactions on Machine Learning Research (02/2026)
Table 2: Parameters used in the numerical experiments.
Time horizon
T 200
Dimension
10
Number of experiments
K 1024
Posterior samples per step
N 64
Initial concentration parameter
A: 16
MH iterations per step PyTorch random seed
G.4
Accuracy of the simulations and confidence intervals
empirical mean
99% confidence interval
50
B
200
$
4
40
40
Cumulativ regret
30
30
20
20
10
10
100
150
200
8 10
T
B
Figure 6: The left sub-figures shows the evolution the empirical mean and 99% confidence intervals of the expected regret with the time sleps T for B E {2, 4). The right sub-figure illustrates the behavior of the empirical mean and 99% confidence intervals of the expected regret at time 200 for values of / ranging in [0.25, 10]. The confidence interval deviates at most by 1.09% from the empirical mean on the left sub-figure and by 1.13% the right sub-figure.
33


Reviews:
[{"review_id": "LH3T15Wfq4", "reviewer": "Reviewer_WQ2H", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the performance of the Thompson Sampling(TS) algorithm in logistic bandit problems using an information-theoretic framework. The main theoretical result shows that the expected regret of TS is bounded by $O(\\frac{d}{\\alpha}\\sqrt{T\\log(\\beta T/d)})$, where $d$ is the problem dimension and $\\alpha$ is a minimax alignment constant characterizing the geometry between the action and parameter spaces. This paper also includes numerical experiments validating the improved regret bounds. \n\nStrengths:\n\n1.\tResult improvement: It provides a regret bound for logistic bandits that avoids exponential dependence on the logistic slope parameter $\\beta$ and does not depend on the number of actions.\n2.\tTechnical innovation: It introduces a refined analysis of the information ratio that lower bounds information via the variance of regret rather than its expectation. \n\nWeaknesses: \n\n1.\tThe paper introduces the minimax alignment constant $\\alpha$ as a key geometric quantity connecting the action and parameter spaces (Sec.2).  Given its central role in the regret upper bound, the authors may provide a more detailed discussion of its practical interpretation and implications.\n2.\tSection 5 is mathematically dense and relies on multiple non-trivial lemmas, which may make the logical flow difficult to follow for readers who are not deeply familiar with information-theoretical analyses of bandit algorithms. \n3.\tIs there a lower bound in the considered setting? Can authors discuss the optimality of  the obtained upper bound in terms dependence on $d$, $\\alpha$, $\\sqrt{T}$ and $\\log (\\beta T/d)$?", "claims_and_evidence_yn": "Yes", "claims_explanation": "The theoretical claims are supported by formal statements and complete proofs (Theorem 2; Proposition 4; Theorem 5, with auxiliary lemmas in Appendices A–D), and the empirical section illustrates the scaling predicted by the theory (Section 6, Figure 3).", "audience_yn": "Yes", "audience_explanation": "TS and bandit algorithms are of broad interest in online learning and reinforcement learning.", "requested_changes": "Please see the summary part. \n\n1.\tSince $\\alpha$ plays a central role in regret upper bound, it would be helpful to include more intuition or examples illustrating its practical meaning.\n2.\tThe authors could improve accessibility by offering more intuitive explanations of key steps of highlighting the main insights behind the lemmas, helping readers better grasp the logic.", "broader_impact_concerns": "NA", "additional_comments": "NA", "extra_scores": {}, "extra_text": {}}, {"review_id": "2H4t3RX5rx", "reviewer": "Reviewer_aXzJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors present a novel analysis for the Thompson Sampling algorithm (TS) for logistic bandit problems, in which one must sequentially select actions from an action space and receive rewards with probability proportionate to the chosen action's alignment to an unknown parameter vector. Their new information theoretic regret bound significantly improves upon previous ones by improving the scaling with respect to the \"scale parameter\", $\\beta$ of the reward distribution from exponential to logarithmic, and removing the dependence on the cardinality of the action set. Additionally, their regret bound does not depend on the \"fragility dimension\", a measure that frequents previous results, which can grow exponentially with the problem dimension. To their knowledge, this is the first such regret bound for any algorithms for logistic bandit problems.\n\nThe core of the authors' results rely on the \"information ratio\", a measure defined as the ratio between the squared expected regret of the algorithm's choice, and the information about the unknown environment parameter gained by it, quantifying the tradeoff between exploration and exploitation. By upper-bounding the information ratio of TS, one can argue that an action that incurs regret is compensated by large information gain. To obtain such an upper bound, the authors first bound both the regret and the information gain in terms of the variance of the regret, as opposed to the expectation as in prior work, avoiding the exponential scaling with $\\beta$, and then show that it suffices to prove the special case of $\\beta \\to \\infty$, thus simplifying the analysis.", "claims_and_evidence_yn": "Yes", "claims_explanation": "To my knowledge, the authors' proofs and claims are supported by sound mathematical evidence. Their results are somewhat surprising - that it is possible to get rid of the dependencies (exponential for $\\beta$ and completely for the cardinality of the set of actions), but the authors' comments in section 4 and 5 supplied good evidence and intuition as to why the readers should believe that their claims are correct. In particular, most of the important claims, theorems, lemmas, and definitions are supplied with textual explanations of their role in the grand scheme of the proof, and the intuitions required to follow the flow of logic, which is a quality I think should be appreciated in academic publications.", "audience_yn": "Yes", "audience_explanation": "The paper presents novel and improved bounds on the regret of Thompson Sampling on logistic bandit problems - both of which very well-celebrated concepts that are quite conceptually simple. Developing such improved bounds, especially one that breaks the dependence on some parameters, whether down from exponential or eliminating completely, would serve to explain the empirical effectiveness of these algorithms and even inspire in their methodology further exploration across the field of machine learning theory on other algorithms and/or problems. From a theorist's perspective, the results presented are those I would like my peers to know about.\n\nIt can be argued that the paper would benefit from an overview of the real-world/industrial applications of Thompson Sampling and/or logistic bandits. Regardless, theoretical advancement in the form of upper/lower bounds are important.", "requested_changes": "As noted above, the paper does not make much statements about the applicational advantage and implications of their improved analytical bounds. While not as necessary as the main results, I would appreciate some more references to industrial applications of Thompson Sampling and/or logistic bandits, as well as discussions about the implications of the authors' results and bounds to application, if any and if applicable.", "broader_impact_concerns": "The work is purely analytical and theoretical and does not require a broader impact statement in my opinion.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "RLRkb0MrF9", "reviewer": "Reviewer_LMvL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents an information-theoretic analysis for logistic bandits and derives new regret bounds for Thompson Sampling. The focus is on theory. The main results look solid.\n\nStrengths.\n\n1. Clear problem setup and tight theoretical development.\n\n2. New regret bounds for Thompson Sampling in the logistic setting.\n\n3. Proofs appear careful and technically sound, and the claims are positioned against prior work.\n\nWeaknesses \n\n1. Numerical experiments are not discussed in depth. How many replications did you choose? Can you also show the confidence intervals?", "claims_and_evidence_yn": "Yes", "claims_explanation": "Yes. The theoretical claims are supported by rigorous proofs and are presented in a clear manner, so the main evidence is convincing from a theory standpoint. While the paper does not provide extensive numerical experiments, the mathematical analysis itself is solid.", "audience_yn": "Yes", "audience_explanation": "Those working on bandit algorithms, reinforcement learning theory, and information-theoretic methods, would likely be interested in these findings, since they provide new regret bounds for TS in the logistic bandit setting.", "requested_changes": "Numerical experiments\n\n1. How many replications did you choose? Can you also show the confidence intervals? This will strengthen your work.\n2. Fig. 3: why is the regret for beta>4 smaller than for beta=2 under TS? A short explanation would help.\n3. Can you (anonymously for now) share your code to justify reproducibility?\n\nIntroduction\n\n4. Table 1: I compared your Table 1 with Faury et al. (2020), *Improved Optimistic Algorithms for Logistic Bandits*. Can you explain the relationship between their kappa and your e^(beta)? The rate of GLM-TSL, and Logistic-UCB-2 appears in both their paper and your work, but it looks not very consistent to me.\n\nProblem Setup\n\n5. Could you clarify what asymptotics your regret bound refers to? In particular, which parameter is taken to infinity in your analysis? For example, is the bound derived in the standard bandit sense where the time horizon T, or does it involve the dimension d,  the parameter norm beta, or some other scaling? A short statement of what limit your results assume would make the presentation clearer. \n\n6. In your setup, beta is a scale parameter known to the agent. Does this mean beta is fixed in the analysis, and if so, how exactly does it help in the regret bound (e.g., avoiding exponential terms like e^(beta))?", "broader_impact_concerns": "I did not find any broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)