acceptodds
Under review as a conference paper at ICLR 2027

Beyond Monotonicity: Thompson Sampling for Convex Ridge Bandits with Polynomial Bayesian Regret

Abstract

Thompson sampling (TS) is a canonical algorithm for Bayesian bandit optimization, yet its theoretical guarantees in nonlinear bandits remain confined to strongly structured settings. In particular, recent work established polynomial Bayesian regret for convex ridge bandits under a monotonicity assumption on the unknown convex link function and posed the open question of whether monotonicity is necessary. We answer this question negatively. We study Bayesian bandit convex optimization with convex ridge losses of the form \(f(x)=\ell(\langle x,\theta\rangle)\), where the link \(\ell\) is convex but not necessarily monotone. For arbitrary priors over bounded, Lipschitz convex ridge losses, any fixed measurable selection of minimizers, and exact-posterior Thompson sampling, we prove a polynomial-in-dimension Bayesian regret bound of \(O(d^9/2n)\). The single-removal John-ellipsoid argument underlying the monotone analysis does not extend to the non-monotone setting. To overcome this obstacle, we develop a cardinality-based analysis of uninformative configurations that combines two-band geometry with a Boolean matrix-rounding argument, yielding an \(O(d^2)\) cardinality bound that is tight up to constants in the large-diameter-to-gap regime. Beyond resolving the open question, our results show that convex ridge structure alone is sufficient for exact-posterior Thompson sampling to achieve polynomial Bayesian regret without link monotonicity. This extends the class of nonlinear bandit problems for which Thompson sampling admits a provable Bayesian regret guarantee, while leaving the optimal dependence on dimension open.

Primary area:
learning theory
Keywords:
Thompson sampling, Bandit convex optimization, Convex ridge functions, Bayesian regret, Information-ratio analysis

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_DfhNOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper analyses the Thompson sampling for a single-index bandit with convex but non-monotonic functions. Building on the open question raised by Bakhtiari et al. (2025) about whether monotonicity is necessary, this paper claims that monotonicity is not necessary and proves an optimal bound except for the order in terms dd.

Critical strengths

The contribution is significant in terms of answering an open question in the literature.

Critical weaknesses

This paper is very difficult to follow. Most of the results are listed only as lemmas, theorems, and propositions, without explaining the background, intuition, interpretations, or insights. I do not understand the implications of extremely large constants in lines 174, 192, and 197. I did not check the proof line by line; however, I do not intuitively understand how they explode so much.

This paper can benefit from a significant rewrite. The presentation could be better.

Many jargons and symbols are used before they are defined.

Questions for authors

Among the listed contributions, I can make sense of the first one, which I feel is the most important. The rest of the contributions seem like just analytical tools you use to establish the regret bound, right? If my understanding is correct, are these analytical tools novel contributions or already existing in the literature?

Is there any practical motivation to analyse non-monotonic bandits? Are there any other algorithms (e.g., UCB-type) that handle this non-monotonic condition?

I might reconsider my score based on the answers by the authors.

3 comments

We thank you for your careful reading and your suggestions on the presentation, contribution hierarchy, and practical motivation. Below, we clarify the role of each result and respond to your questions about the constants and related algorithms.

Main contribution and the role of the other results.

Your reading of the hierarchy is correct: the main result is the regret guarantee for exact TS without monotonicity. The geometric and linear-algebraic results are the tools that establish it. The revised introduction now distinguishes them explicitly:

  • Established here: the two-band and Boolean-masking argument, the cardinality bound and quadratic-size construction, the counterexample to the literal ellipsoid dichotomy, and the value-based, minimiser-preserving transfer construction.
  • Borrowed with attribution: the information-ratio framework of Russo and Van Roy [RVR16]; the decomposition and blocking arguments of Bakhtiari et al. [BLS25]; and the trace–rank inequality [Alon09]. The rounding lemma is elementary, and we do not claim priority for its general linear-algebra statement.

The revised rate is O~(d7/2n)\widetilde O(d^{7/2}\sqrt n), improving the submitted O~(d9/2n)\widetilde O(d^{9/2}\sqrt n). The optimal dimension dependence remains open.

Why the proof and its constants grow.

The roadmap after the main results now gives the dependency chain and the source of each dimension factor: two-band geometry gives a configuration bound O~(d2)\widetilde O(d^2); blocking produces tuples of size O~(d3)\widetilde O(d^3); the decomposition lemma squares that size, giving a coefficient O~(d6mα)\widetilde O(d^6m_\alpha); taking the square root in the regret transfer and including the cover entropy gives d3d=d7/2d^3\sqrt d=d^{7/2}.

The constants are explicit so that each step can be checked; their numerical values have not been optimised. The main text now keeps their parameter structure: the regret prefactor is 384cdωd384c_d\omega_d, with 384=6⋅4⋅16384=6\cdot4\cdot16, and the certificate lower bound uses α≤ε/4\alpha\le\varepsilon/4. The expanded constants for the alternative c=96(d+1)c=96(d+1) choice and the small-α\alpha threshold are retained in Appendices B and D. Proposition 3.5 now foregrounds the parameter regime used by the main theorem. This does not make the finite-horizon guarantee numerically sharp: it becomes smaller than the trivial regret bound only at horizons of order d7d^7 times large constants and logarithmic factors. The paragraph after Theorem 3.1 states this limitation.

Changes that make the argument easier to follow.

The abstract now describes the ellipsoid obstruction and the matrix argument before using compressed technical labels. Section 1 introduces the decision problem, the link function and the motivation before listing contributions, and explains an uninformative configuration at its first use. Section 2 explains the information-ratio certificate, distinguishing posterior variance from the finite-label mutual information used in the transfer. Sections 3–5 explain what is being counted, why the two bands arise and what the mask removes before giving the formal statements. We also corrected a misleading simplification: an “uninformative” configuration has small off-diagonal deviations at the specified tolerance; it does not provide literally zero information.

References

[RVR16] Daniel Russo and Benjamin Van Roy. An Information-Theoretic Analysis of Thompson Sampling. Journal of Machine Learning Research, 17(68):1–30, 2016.

[BLS25] Alireza Bakhtiari, Tor Lattimore, and Csaba Szepesvári. Thompson Sampling for Bandit Convex Optimisation. In Proceedings of Thirty Eighth Conference on Learning Theory, Proceedings of Machine Learning Research, volume 291, pp. 231–263. PMLR, 2025.

[Alon09] Noga Alon. Perturbed Identity Matrices Have High Rank: Proof and Applications. Combinatorics, Probability and Computing, 18(1–2):3–15, 2009.

Practical motivation for non-monotone links.

Target-tracking losses such as (⟨x,θ⟩−s0)2(\langle x,\theta\rangle-s_0)^2 and ∣⟨x,θ⟩−s0∣|\langle x,\theta\rangle-s_0| penalise both undershooting and overshooting a target. If that target is inside the projection interval, these links are convex and non-monotone. On a compact action set they can be rescaled to meet our boundedness and Lipschitz assumptions. Monotone ridge losses admit a boundary minimiser, whereas these target losses can have an interior optimal index. Our contribution is a statistical foundation for exact posterior sampling in this setting; we make no computational or empirical-performance claim.

Other algorithms, including UCB-type methods.

Yes. Dey, Bhore and Ghosh (2026) [DBG26], Optimal Regret for Single Index Bandits, analyse ZoomSIB-UCB for unknown, possibly non-monotone links in a contextual model, with O~(T2/3)\widetilde O(T^{2/3}) frequentist regret for fixed dimension under their assumptions. Kang et al. (2026) [Kang26] give Stein-estimator-based methods for contextual single-index models. Lattimore (2021) [Lattimore21] proves a nearly O(dn)O(d\sqrt n) minimax bound in a related adversarial ridge model with normalised domain and observed loss values. These are different models or algorithms; they do not establish the guarantee for exact TS with Bernoulli observations that we study. Section 1 and Appendix F now make this distinction explicit.

References

[DBG26] Devdan Dey, Sujoy Bhore, and Avishek Ghosh. Optimal Regret for Single Index Bandits. arXiv preprint 2605.09454, version 3, 2026.

[Kang26] Yue Kang, Mingshuo Liu, Bongsoo Yi, Jing Lyu, Zhi Zhang, Doudou Zhou, and Yao Li. Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions. International Conference on Learning Representations, 2026.

[Lattimore21] Tor Lattimore. Minimax Regret for Bandit Convex Optimisation of Ridge Functions. arXiv preprint 2106.00444, version 2, 2021.

Thank you for the revisions. I raise my score by 1. However I am still leaning towards rejection.

Reviewer_BHxROpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates the Bayesian regret of Thompson Sampling (TS) for convex ridge bandits. Previous work by Bakhtiari et al. (2025) established polynomial Bayesian regret bounds for TS under the additional assumption that the link function is monotone. The paper removes the monotonicity and proves a bound of O(d9/2n1/2)O(d^{9/2}n^{1/2}).

Critical strengths

The paper tackles a technically sound and interesting question of Bayesian methods on convex reward bandits. It extends the proof techniques of former work on monotonic functions, and resolves a concrete open problem.

Critical weaknesses

The factor d8d^8 information-ratio coefficient is unsatisfying and point to extensive burn-in and regret complexity. The argument in establishing the bound is a little conservative. First, the authors treat configurations using an arbitrary convex function, rather than fully exploiting the fact that the function is the actual posterior mean. Second, the argument converts a worst-case guarantee on the existence of informative pairs into an average information lower bound. It does not take full advantage of the posterior probabilities associated with different functions. A convex function is the sum of two monotonic function. I don't know whether a two-sided version of the monotone geometric argument help solving the problem.

Questions for authors

Q1. Is there any evidence that the deterioration from (d^{5/2}) to (d^{9/2}) is unavoidable for non-monotone convex ridge functions? In particular, can the authors construct a family of priors for which TS exhibits provably larger regret than in the monotone setting?

1 comment

We thank you for your careful review and for your questions about dimension dependence, posterior weights, and the scope of the lower bounds. We address these points below, distinguishing the improved upper bound from the questions that remain open.

Dimension dependence and the d8d^8 coefficient.

We have reduced the information-ratio coefficient to O(d6log⁡3d mα)O(d^6\log^3 d\,m_\alpha) and the regret to O~(d7/2n)\widetilde O(d^{7/2}\sqrt n) (Theorems 3.4 and 3.1). The new rounding lemma permits a tolerance parameter cd=Θ(log⁡d)c_d=\Theta(\sqrt{\log d}) instead of 96(d+1)96(d+1). This is a proved improvement of the upper bound, not a claim of optimality.

Q1 — Is worse regret than the monotone rate [BLS25] unavoidable?

We cannot establish that it is unavoidable, and we have no prior separating the two regret rates. Our quadratic cardinality construction and the one-step coefficient lower bound β≥d(d+1)/8\beta\ge d(d+1)/8 do not provide such a regret separation. Section 9 now states this directly; whether the monotone d5/2d^{5/2} dependence is achievable remains open.

Using the actual posterior mean and posterior probabilities.

Proposition D.2 shows that a d(d+1)d(d+1)-element configuration can have an actual prior mean as its comparison function, but the weights matter. At the submitted c=96(d+1)c=96(d+1), the sufficient construction gives the configuration total mass at most 4d/(387d+384)4d/(387d+384), leaving about 99% on a constant loss even at the largest guaranteed configuration mass. At the revised parameter, cd=96c_d=96 for d<2109d<2^{109}, so the uniform prior works for 384≤d<2109384\le d<2^{109}. For 2≤d<3842\le d<384, Proposition D.2 gives the sufficient choice w≤4d/(384+3d)w\le4d/(384+3d). In general, d≥4cdd\ge4c_d permits w=1w=1. These are existence statements about configurations, not statistical hardness results.

Your point about posterior weights remains relevant. The current proof finds informative pairs in a tuple of k=Θ~(d3)k=\widetilde\Theta(d^3) losses, credits each pair only with the minimum threshold energy, and then pays k2k^2 in the decomposition lemma. The prior-mean construction does not show that this conversion is tight. A posterior-weighted estimate of average energy could improve the certificate without contradicting any of our lower bounds. We now identify this as a possible source of slack, rather than asserting that either of the relaxations you identified is harmless.

A two-sided monotone argument.

The two-band lemma is precisely a two-sided geometric statement: the other selected minimisers can occupy a band on each side of a loss's minimiser. The step that fails to carry over literally is the single-removal volume decrease. Proposition 3.6 gives a twelve-point configuration for which every single deletion leaves the John ellipsoid unchanged, at every smoothing radius. This explains our replacement by Boolean masking. It does not rule out a different two-sided potential, and decomposing the link into monotone components alone does not decompose TS into separate algorithms for those components.

References

[BLS25] Alireza Bakhtiari, Tor Lattimore, and Csaba Szepesvári. Thompson Sampling for Bandit Convex Optimisation. In Proceedings of Thirty Eighth Conference on Learning Theory, Proceedings of Machine Learning Research, volume 291, pp. 231–263. PMLR, 2025.

Reviewer_ZqBaOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proves O~(d9/2n)\widetilde{O}(d^{9/2}\sqrt{n}) Bayesian regret for exact Thompson sampling on convex ridge losses without monotone links, resolving an open question from Bakhtiari et al. (2025). The main contribution is an O(d2)O(d^2) cardinality bound using two-band geometry and Boolean masking. A selection-preserving transfer converts this into regret, while explicit constructions establish cardinality tightness and the failure of the previous ellipsoid argument.

Critical strengths
  • S1. Resolving a clear theoretical question. The result establishes that convex ridge structure suffices for polynomial Bayesian regret of exact TS without monotonicity. This meaningfully extends the earlier monotone-link guarantee.

  • S2. A substantive new proof mechanism. Boolean masking controls highly imbalanced two-sided configurations that obstruct the previous approach. The matching-order cardinality construction and explicit ellipsoid counterexample substantiate the technical contribution. The central arguments appear correct.

Critical weaknesses
  • W1. Weak dimension dependence. The O~(d9/2n)\widetilde{O}(d^{9/2}\sqrt{n}) bound and large constants make the guarantee primarily qualitative. The proof requires c=Θ(d)c=\Theta(d), which increases the number of blocks and contributes to the gap from the monotone rate. Whether this dimension-dependent tolerance is necessary remains unresolved.

  • W2. The transfer theorem’s independent significance needs clearer positioning. Nonunique minimizers also occur for monotone convex links, and an arbitrary fixed selection is compatible with the earlier consistent tie-breaking convention. The paper explains its new construction, but could distinguish more precisely between a stronger justification of the transfer and an expansion of the covered selection rules. This is a minor positioning concern, not a soundness objection.

  • W3. Structural tightness does not establish statistical tightness. As acknowledged in Section 9, the cardinality construction uses an external comparison function rather than the posterior mean required by the regret analysis. Proposition D.1 gives only an Ω(d2)\Omega(d^2) certificate lower bound against the O(d8log⁡(1/α))O(d^8\log(1/\alpha)) upper bound. Thus, the lower bounds do not establish an intrinsic statistical cost of removing monotonicity.

Questions for authors
  • Q1 (W1). Can the O(d2)O(d^2) cardinality bound hold uniformly in D/εD/\varepsilon for a fixed cc, such as c=12c=12? This would yield an O(d6log⁡(1/α))O(d^6\log(1/\alpha)) blocking certificate and O~(d7/2n)\widetilde{O}(d^{7/2}\sqrt{n}) regret. Alternatively, is there a configuration showing that fixed cc requires a larger cardinality bound?

  • Q2 (W2). Does the selection-preserving transfer recover the earlier O~(d5/2n)\widetilde{O}(d^{5/2}\sqrt{n}) rate for arbitrary fixed measurable selections on the monotone subclass, for example through a one-sided infimal-convolution kernel? What precisely does this add beyond the earlier consistent tie-breaking convention?

  • Q3 (W3). Can a matching-order cardinality construction remain uninformative when its comparison function is the mean of an actual prior, at the theorem’s tolerance? Such a construction, or a stronger prior-level certificate lower bound, would help distinguish a statistical obstruction from slack in the proof.

2 comments

We thank you for your careful reading and detailed technical questions on the dimension dependence, monotone recovery, and prior-mean configurations. We address these three points in turn, beginning with the direct answers.

  • Q1: We obtain the suggested regret exponent up to logarithmic factors; the fixed-cc, all-dimensional O(d2)O(d^2) cardinality question remains open.
  • Q2: We recover O~(d5/2n)\widetilde O(d^{5/2}\sqrt n) on the monotone subclass. The added contribution is a self-contained proof, not a larger class of fixed selection rules.
  • Q3: A genuine prior mean exists, but at the submitted c=96(d+1)c=96(d+1) even its largest guaranteed configuration mass leaves about 99% on a constant loss.

Q1 / W1 — Fixed tolerance and dimension dependence.

Write h=d+1h=d+1, ωd=4+⌈log⁡2h⌉\omega_d=4+\lceil\log_2h\rceil and cd=max⁡{96,⌈9ωd⌉}c_d=\max\lbrace 96,\lceil9\sqrt{\omega_d}\rceil\rbrace. Theorems 3.3(a), 3.4 and 3.1 give

  • Configuration size: ∣C∣<2ωdh2(c≥cd)|C| < 2\omega_dh^2\quad(c\ge c_d).
  • Information-ratio coefficient: β≤1024cd2ωd2h6mα\beta\le1024c_d^2\omega_d^2h^6m_\alpha.
  • Bayesian regret: BReg⁡n=O~(d7/2n)\operatorname{BReg}_n=\widetilde O(d^{7/2}\sqrt n).

The count is uniform in D/εD/\varepsilon. The improvement is Lemma 5.3: an m×mm\times m minor has at most mm original diagonal entries, so diagonal error 1/21/2 contributes at most m/4m/4 to its squared Frobenius error. Treating it separately from off-diagonal error gives the rank bound needed for the mask; Section 5.2 gives the full argument.

Although cd=96c_d=96 for d<2109d < 2^{109}, asymptotically it is Θ(log⁡d)\Theta(\sqrt{\log d}). Thus the exact all-dimensional O(d2)O(d^2) assertion for a single fixed cc, including c=12c=12, remains open. We also have no fixed-cc construction requiring superquadratic cardinality.

Q2 / W2 — Monotone recovery and what the transfer adds.

There is no increase in the generality of the fixed selection rules: the contribution is a self-contained proof that avoids requiring compatibility between selections of an original loss and its rotated proxy. Arbitrary fixed measurable selections already fit the convention in Bakhtiari et al. [BLS25], Section 1 (Notation).

Our cells use function values. On the monotone subclass, the one-sided kernel you suggested gives

gf(x)=min⁡y∈K[f(y)+max⁡{⟨θκ,x−y⟩,0}]g_f(x)=\min_{y\in K}\left[f(y)+\max\lbrace \langle\theta_\kappa,x-y\rangle,0\rbrace\right].

It preserves monotonicity, satisfies f−ρ/2≤gf≤ff-\rho/2\le g_f\le f, and keeps the originally selected xfx_f as an exact minimiser. Corollary 7.3 therefore recovers O~(d5/2n)\widetilde O(d^{5/2}\sqrt n) for every fixed measurable selection. Appendix C verifies the required uniformity of Bakhtiari et al.'s Theorem 7 [BLS25] under the explicit hypotheses of their Lemma 8, including flat links (both in Section 4). Their cover is Definition 22 and Proposition 24; their general transfer is Theorem 28, all in Appendix F. History-dependent selection rules remain outside our theorem.

Q3 / W3 — Prior-mean configurations and their limitations.

Proposition D.2 gives a sufficient prior with total mass ww uniformly on the N=d(d+1)N=d(d+1) losses and mass 1−w1-w on the constant loss 1/41/4, where

0<w≤w0=min⁡{1,4d/(4c+3d)}0 < w\le w_0=\min\lbrace 1,4d/(4c+3d)\rbrace.

It retains the same configuration, tolerance and gap scale. At the submitted c=96(d+1)c=96(d+1), w0=4d/(387d+384)<4/387w_0=4d/(387d+384) < 4/387: even at the largest guaranteed ww, about 99% remains on the constant loss. This is an existence result, not a statistically hard prior established by the argument. The stated weight bound is sufficient, not claimed necessary for all constructions.

For the revised parameter, cd=96c_d=96 when d<2109d < 2^{109}. Thus 384≤d<2109384\le d < 2^{109} permits the uniform prior (w=1w=1); for 2≤d<3842\le d < 384, the proposition gives the sufficient choice w≤4d/(384+3d)w\le4d/(384+3d). In general, d≥4cdd\ge4c_d permits w=1w=1.

Conversely, a mean supported entirely on an uninformative configuration requires more than c(d+1)/2c(d+1)/2 elements (Proposition D.2(b)); Theorem 3.3(b) rules this out at c=96(d+1)c=96(d+1), so some outside mass is necessary there. None of these statements establishes statistical tightness or excludes improvement from posterior weights. The coefficient lower bound remains β≥d(d+1)/8\beta\ge d(d+1)/8 in the small-α\alpha range of Proposition D.1, and we have no stronger regret lower bound.

References

[BLS25] Alireza Bakhtiari, Tor Lattimore, and Csaba Szepesvári. Thompson Sampling for Bandit Convex Optimisation. In Proceedings of Thirty Eighth Conference on Learning Theory, Proceedings of Machine Learning Research, volume 291, pp. 231–263. PMLR, 2025.

Thank you for your detailed response. I welcome the improved rate of O~(d7/2n)\tilde{O}(d^{7/2}\sqrt{n}). However, I would like to review Lemma 5.3 and Theorems 3.3–3.4 in the revised manuscript, so I kindly ask the authors to upload the updated version. For W2, my concern is resolved by your clarification that the scope of the selection rule has not been broadened and that the primary contribution here is the self-contained proof. As you have acknowledged, statistical tightness has not been demonstrated, which remains a limitation of this work. Consequently, I will maintain my current score of 2

Comments on the paper

1 comment

We thank the reviewers for their careful reading and constructive feedback. Our main contributions and responses to the key concerns are:

  • Polynomial regret does not require a monotone link. We prove a polynomial Bayesian regret guarantee for exact Thompson sampling on bounded, Lipschitz convex ridge losses without monotonicity, for any prior and any fixed measurable choice of minimisers under Bernoulli observations (Theorem 3.1). This covers target losses that penalise both undershooting and overshooting.

  • A sharper bound addresses the dimension-dependence concern (ZqBa, BHxR). A rounding lemma that separates diagonal and off-diagonal errors gives an O(d2log⁡d)O(d^2\log d) configuration bound and improves the regret from O~(d9/2n)\widetilde O(d^{9/2}\sqrt n) to O~(d7/2n)\widetilde O(d^{7/2}\sqrt n) (Lemma 5.3; Theorems 3.3–3.4). This achieves the suggested regret exponent up to logarithmic factors; the exact O(d2)O(d^2) configuration bound for a single fixed tolerance parameter in all dimensions remains open.

  • The proof recovers the earlier monotone rate (ZqBa). A one-sided approximation preserves the originally selected minimisers and recovers O~(d5/2n)\widetilde O(d^{5/2}\sqrt n) on the monotone subclass (Corollary 7.3; see [BLS25] for the earlier rate). The contribution is a self-contained transfer proof that avoids a selection-compatibility requirement between the original loss and its rotated proxy; it does not enlarge the class of fixed selection rules.

  • A counterexample explains why the earlier geometric step cannot simply be reused (BHxR). Our twelve-loss construction in dimension three leaves the John ellipsoid unchanged after every single deletion (Proposition 3.6). This disproves the literal single-removal shrinkage step for non-monotone losses. We replace that step with two-band geometry and a matrix argument; the counterexample does not rule out other two-sided potentials.

  • The quadratic-size examples can use genuine prior means (ZqBa, BHxR). Proposition D.2 realises these configurations with an actual prior mean. With the revised parameters, a uniform prior works for 384≤d<2109384\le d<2^{109}; with the submitted parameters, our sufficient construction still leaves about 99% of the mass on a constant loss. This resolves the existence question, but does not establish statistical hardness or prove that non-monotonicity requires worse regret.

  • The revised paper makes the contribution and proof dependencies explicit (DfhN). The roadmap links two-band geometry to configuration counting, the information-ratio bound, and finally regret, and identifies where each dimension factor enters. We separate new arguments from borrowed tools, explain the target-loss motivation, and state that the constants are explicit but unoptimised. The finite-horizon limitations and unresolved optimal dimension dependence are also stated directly.

References

[BLS25] Alireza Bakhtiari, Tor Lattimore, and Csaba Szepesvári. Thompson Sampling for Bandit Convex Optimisation. In Proceedings of Thirty Eighth Conference on Learning Theory, Proceedings of Machine Learning Research, volume 291, pp. 231–263. PMLR, 2025.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.