Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds

Arda G\"u\c{c}l\"u; Subhonmesh Bose

REVIEW 2 major objections 4 minor 40 references

Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read TRAiL perturbs the optimal action along the tangent plane to guarantee both √T-order inference and order-optimal regret in linear bandits.

desk verdict A novel forced-exploration scheme with a real but probably fixable proof gap at the heart of its inference guarantee; worth sending to referees. read the letter →

arxiv 2411.12154 v1 pith:P536427A submitted 2024-11-19 stat.ML cs.LGcs.SYeess.SY

Arda Güçlü , Subhonmesh Bose This is my paper · ORCID

classification stat.MLcs.LGcs.SYeess.SY MSC 62L0562C20

keywords linearbanditsforcedexplorationtangentialrandomizationinferencequalityregretboundsmatrixmartingalesminimaxlowerboundstronglyconvexactionsets

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

TRAiL is a linear bandit algorithm that, at each step, takes the action that maximizes expected reward under the current least-squares estimate, adds a random perturbation within the tangent plane of the action set, and projects back onto the set. The paper proves that with high probability the smallest eigenvalue of the design matrix grows as Ω(√T), giving an inference error bound that shrinks as 1/√t, and that cumulative regret is O(√T log T). It then proves a minimax lower bound of Ω(√T) for any algorithm on a wide class of action sets and noise models, via a Bayesian Cramér–Rao (van Trees) argument. The central trade-off is that cumulative regret and inference quality multiply to at least T: an algorithm with O(T^α) regret must have Ω($T^{{1−α}}$) inference quality. If correct, TRAiL is order-optimal up to log factors and shows that forced exploration can guarantee inference and control simultaneously.

What carries the argument

The mechanism is tangential randomization: at each round, TRAiL solves a convex program for a*(θ̂_t), finds an orthonormal basis whose first vector is the surface normal (which Lemma 1 shows is proportional to θ̂_t), perturbs along the remaining basis vectors by independent subgaussian random variables with variance D/√t, and projects back to A. The geometry of strongly convex sublevel sets (Lemmas 2–4) ensures the projection error is O(m²) and that per-round regret is quadratic in the action distance, while a matrix Freedman inequality (Lemma 9, adapted from Tropp) controls the matrix martingale ata_t^T − E[ata_t^T] so that the eigenvalue lower bound in Lemma 7 transfers from expectation to high-probability V_t.

What would settle it

Simulate TRAiL on a strongly convex sublevel set where θ̂_t is forced (by initialization or adversarial noise) to lie outside the parameter set Θ for the first F(δ) rounds; if λ_min(V_T) fails to grow as √T with high probability, the geometric lemmas' requirement that estimates remain in Θ is load-bearing. Alternatively, run a regret-optimal algorithm on an L^p ball with p > 2 and measure regret × λ_min(V_T) empirically: if the product stays below cT permanently in the long run, the asymptotic trade-off (Regret)(Inference) ≳ T is false.

Watch

Extended reading notes

Core claim

The paper's central discovery is that random exploration confined to the tangent plane of the optimal action—with perturbation variance decaying as 1/√t—forces the design matrix of a linear bandit to fill all directions at the rate λ_min(V_T) ≳ √T with high probability (Theorem 6). This inference guarantee directly yields a high-probability regret bound O(√T log T) (Theorem 12). Equally central, the paper proves a trade-off: over any policy, the cumulative regret and the minimum-eigenvalue inference quality satisfy (regret)(inference) ≳ T in a Bayesian sense (Theorems 13 and 15), implying an Ω(√T) minimax lower bound for a broad family of action sets and noise distributions. As a corollary, regret-optimal control cannot be achieved with inference that is too slow or too fast; the rates must match.

Load-bearing premise

The geometric lemmas that give the projection and regret bounds are proved for actions in A* and parameters in Θ, but the paper never shows that the RLS estimates θ̂_t (and hence the actions a*(θ̂_t)) stay in Θ before the high-probability event in Theorem 6 starts.

Editorial extensions

If this is right

If TRAiL's guarantees hold, linear bandits on strongly convex sublevel sets admit a single algorithm that gives both high-probability inference and order-optimal regret without separate exploration/exploitation phases.
Any algorithm that achieves O(T^α) expected regret must accumulate Ω(T^{1−α}) inference quality, so "free" inference is impossible: regret and inference rates are locked together.
The minimax regret lower bound Ω(√T) extends to general action sets and noise processes with finite Fisher information I_ε, not just spheres or L^p balls.
Empirically observed "cheap control" on L^p balls—near-optimal regret with poor inference—is transient and must vanish asymptotically for smooth strongly convex sets.
The proof technique also yields high-probability regret and inference guarantees for the earlier FEL forced-exploration algorithm, as shown in Appendix B.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The regret–inference product inequality suggests a design heuristic for adaptive experiments: when the goal is both optimization and estimation, choose exploration noise so that information accumulation tracks the regret rate, rather than maximizing information independently.
The transient 'illusion' on L^p balls implies that finite-horizon comparisons of bandit algorithms that focus only on regret may miss inference deficits that become decisive asymptotically; evaluating both metrics is safer.
The matrix-martingale deviation argument may transfer to other forced-exploration schemes (e.g., posterior sampling variants) and to adaptive control settings such as LQR, where a similar inference–control trade-off is being studied.
A testable quantitative prediction: for any policy with exactly O(T^α) regret on a strongly convex action set, the empirical product (regret × λ_min(V_T)) should stay above a constant multiple of T over long horizons once the burn-in phase ends.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: this is a genuinely new forced-exploration scheme for linear bandits, with a clean geometric idea and a useful inference-regret tradeoff. But the paper as written has a load-bearing proof gap: Lemma 7 applies Assumption 3 to a*(theta_hat_t) without ever showing the RLS estimate stays in Theta. I think the gap is fixable, but it needs to be fixed before the guarantees are taken as established.

What's actually new: the tangential random walk plus projection is a neat alternative to FEL; the matrix-martingale argument for lambda_min(V_t) = Omega(sqrt(t)) on strongly convex sublevel sets is new to me; and the van Trees-based lower bound yielding the regret-inference product constraint is a solid contribution. The experiments on ellipsoids are honest, and Section 9's discussion of Lp balls is a thoughtful treatment of why short-run behavior can look like it violates the tradeoff. No circularity: the bounds are derived, not fitted.

Soft spots, in order of seriousness: 1. Lemma 7's domain mismatch. The proof of (59) uses Assumption 3(b)-(c) at a*(theta_hat_s), including the norm lower bound and the angle condition (9). But theta_hat_s is an unconstrained RLS estimate; nothing in Algorithm 1 or the assumptions keeps it in Theta. The stress-test note has this right. It's likely fixable by splitting the sum into a burn-in period and a post-F(delta) period, since the burn-in contribution is O(sqrt(log)) and can be absorbed into c2. But as written, the proof is incomplete. 2. Lemma 9, the modified matrix Freedman inequality, is stated without proof. If it is truly a minor variant of Tropp, putting the derivation in the appendix would settle it. In a paper where the main result hinges on it, omitting it is a bad look. 3. The 'universal' lower bound rests on Assumption 5(a), which the authors themselves note can fail for Lp balls at large p. So the universality claim should be softened.

Minor: the experiments tune D beyond what Assumption 4 allows; that is fine for practice but means the empirical section does not validate the theory's regime.

Bottom line: the paper is worth a serious referee. I would send it out, with instructions to the authors to supply the proof of Lemma 9 and to close the theta_hat_t not-in-Theta gap in Lemma 7. If the fixes check out, this is a solid paper. If not, the central inference guarantee is unproven.

Referee Report

2 major / 4 minor

Summary. The paper introduces TRAiL, a forced-exploration linear bandit algorithm for action sets that are sublevel sets of strongly convex functions. At each round, TRAiL computes an RLS estimate θ̂_t, selects the myopic maximizer a⋆(θ̂_t), perturbs it randomly along the tangent plane, and projects back onto the action set. The main theoretical claims are: (i) under Assumptions 1–4, λ_min(V_t) = Ω(√t) with high probability, yielding the inference guarantee in Theorem 6 that ‖θ̂_{t+1} − θ⋆‖² ≤ O(log(t/δ)/√t) simultaneously over t; (ii) a high-probability regret bound R_θ⋆(T) = O(√T log T) in Theorem 12; and (iii) a minimax lower bound Ω(√T/I_ε) in Theorem 15, derived through a van Trees inequality, together with an inference-regret trade-off of the form E[R]·λ_min(E[V_T]) ≳ T. The paper also presents experiments on ellipsoidal action sets and on L^p balls, including a discussion of why apparent violations of the trade-off on A_10 are transient.

Significance. If the Section 5 proof gaps are repaired, this is a strong contribution: TRAiL is computationally lightweight, explores and exploits simultaneously, and the paper promises simultaneous high-probability inference guarantees and order-optimal regret for a broad class of strongly convex sublevel-set action spaces. The matrix-martingale treatment of λ_min(V_t) and the van Trees lower bound connecting regret and inference quality are genuinely novel directions for linear bandits. The paper also provides a useful discussion, supported by experiments, of how near-non-smooth action sets such as L^p balls with large p can exhibit transient apparent violations of the inference-regret trade-off. The empirical section is suggestive rather than exhaustive, but it is clearly reported. The main reservations are technical and concentrated in Section 5, where the concentration argument currently does not go through as written.

major comments (2)

[Section 5, Lemma 7 (Eqs. (57), (59), (71))] The proof of Lemma 7 applies Assumption 3 and Lemma 3 to a⋆(θ̂_s) at every time s, but Assumption 3 is stated only for a ∈ A⋆(m′) and Lemma 3 only for a ∈ A⋆. The RLS estimate θ̂_s = V_{s−1}^{-1}Σ_{j<s} a_j Y_j is an unconstrained vector; nothing in Algorithm 1 or in Assumptions 1–4 keeps θ̂_s in Θ, and before the high-probability event of Theorem 6 begins at F(δ) there is no control over θ̂_s. Consequently, Eq. (71), the bound m_φ/a⋆(θ̂_s) ≤ m_φ/a_min in Step 2, and the projection bound borrowed from Lemma 3 are not justified for arbitrary s. This is load-bearing: the per-step lower bound (59) is the deterministic source of the Ω(√t) growth in λ_min(V_t) used in Lemma 10 and hence in Theorem 6. The same domain issue recurs in the proof of Theorem 12, where Lemma 4 is applied to θ̂_{t+1} even though Lemma 4 is stated only for θ_1, θ_2 ∈ Θ. A repair requires either a separate argument that θ̂_s stays in Θ, or a modification of the algorithm such as using a⋆(proj_Θ θ̂_t), or an explicit two-stage argument in which the rounds before F(δ) are absorbed into the additive constant c_2.
[Section 5, Lemmas 9–10 (Eqs. (83)–(86))] Lemma 9, the modified matrix Freedman inequality on which the entire high-probability inference guarantee rests, is stated without proof. Since it is a custom adaptation of Tropp's inequality rather than a verbatim quotation, the proof or an exact statement of the modification should appear in the manuscript. More seriously, the application of Lemma 9 in Lemma 10 is not correct as written. Lemma 8 bounds the predictable quadratic variation Σ_{s=1}^t E_{s−1}[(E_{s−1}[a_sa_s^T] − a_sa_s^T)^2], but Eq. (86) claims ||Σ_{s=1}^t (X_s)^2|| ≤ Cψ_t almost surely and then uses this random quadratic variation in the Freedman event. Since each X_s is bounded by 2a_max², the random sum can be O(t), not O(√t). If the intended event in Lemma 9 is the predictable quadratic variation, then Eq. (86) and the sentence 'Lemma 8 allows us to infer' must be rewritten accordingly; as written, the deduction of Eq. (87) does not follow.

minor comments (4)

[Section 6, proof of Theorem 12] The index shift between a_t and θ̂_{t+1} should be made explicit: Eqs. (92)–(95) provide bounds for a⋆(θ̂_{t+1}), while the regret sum in Eq. (100) is over t = ⌊√T⌋+1 to T for actions a_t. The argument is likely salvageable by relabeling, but as written the matching of indices is unclear.
[Section 8, heading] The heading 'Emprical Comparison with Other Algorithms' contains a typo and should read 'Empirical'.
[Section 3, Eq. (13)] The notation t ∼ log_2(1/δ) is informal; please state explicitly the range of t, e.g., t ≥ F(δ) for a specific function F, as is done in Theorem 6.
[Section 9] The sentence 'with 1/log t log(λ_min(V_t)) → 0.4 within 5000 iterations' mixes a limiting statement with a finite-time empirical observation; please clarify whether this is a fitted finite-sample slope or an asymptotic claim.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: TRAiL's inference and regret bounds follow from its stated exploration schedule and external concentration/CRB results, not from fitted inputs or self-citations.

full rationale

TRAiL's derivation chain is self-contained. The Theorem 6 inference guarantee is not a fitted prediction: the perturbation variance D/t^{1/2} in Assumption 4 is a design input, and Lemma 7 algebraically converts that schedule into λ_min(Σ_s E_{s-1}[a_s a_s^T]) ≥ D c0 √t − c2 (Eq. 57), with c0 and c2 built from geometric constants and D; no parameter is fitted to the target theorem. The martingale concentration step (Lemma 9) is an external matrix Freedman bound from Tropp (2011), and the confidence ellipsoid (Lemma 11) is the standard external result from Abbasi-Yadkori et al. (2011); neither is a self-citation, and the paper does not invoke a uniqueness theorem of its own to force its algorithmic choice. The regret upper bound Theorem 12 combines the inference guarantee with Lemma 2 and Lemma 4, both proved from Assumptions 1 and 3, and the perturbation tail bound is an independent Chernoff argument. The lower bound Theorem 15 uses the van Trees inequality from Ziemann and Sandberg (2021) and its own Theorem 13, which is proved independently through a Taylor expansion and a deterministic regret-to-inference inequality; no load-bearing step relies on a self-citation. D is tuned only in the experimental section, not in the theoretical result; the theory states a constraint (Assumption 4, Eq. 12) rather than fitting D to manufacture the Ω(√T) conclusion. I could not exhibit any equation in which a predicted quantity equals an input by construction, nor any fitted constant relabeled as a prediction. Two genuine proof-quality concerns exist but are not circularity: Lemma 7 applies Assumption 3 to a⋆(θ̂_s) for the unconstrained RLS estimate θ̂_s, without proving θ̂_s ∈ Θ, and Lemma 9 is stated with its proof omitted as 'minor variations' to Tropp (2011). These are correctness risks and should be addressed, but they do not make the derivation circular.

Assumptions & free parameters 1 free parameters · 8 assumptions · 0 invented entities

The central theoretical results rest on a substantial set of domain assumptions (Assumptions 1-5) on the parameter space, noise, and action-set geometry, plus external concentration and information inequalities. The main algorithm parameter D is tuned in experiments. No new physical or conceptual entities are introduced. The lower bound additionally needs the uniform eigenvalue separation in Assumption 5(a), which is the main restriction on the advertised universality.

free parameters (1)

D (perturbation variance scale) = tuned values 0.1, 0.5, 0.3, 0.03 across experiments; theory requires D to satisfy Assumption 4
Controls exploration magnitude in Algorithm 1. In theory it is a chosen hyperparameter bounded by geometry; in experiments it is fit by grid search and the bound is disregarded.

assumptions (8)

domain assumption Assumption 1: The true parameter theta_star lies in a bounded set Theta with theta_min > 0 and theta_max < infinity.
Used throughout to bound regret and to ensure reward-maximizing actions are unique and well-aligned with gradients.
domain assumption Assumption 2: Zero-mean M-subgaussian noise with E_{t-1}[Y_t] = theta_star^T a_t.
Standard noise model needed for the RLS confidence ellipsoid and the high-probability inference theorem.
domain assumption Assumption 3: The action set is the sublevel set of a 3-times differentiable strongly convex function g with uniform gradient and Hessian bounds on A_star(m') and an alignment condition between actions and normals.
Backbone of Lemmas 1-5 and all geometric bounds, including the quadratic regret bounds and projection error control.
domain assumption Assumption 4: Perturbations are D/sqrt(t)-subgaussian, symmetric, with second moment D/sqrt(t) and D bounded by a geometric quantity.
Needed for the per-step eigenvalue lower bound in Lemma 7 and the quadratic variation bound in Lemma 8.
domain assumption Assumption 5: Uniform positivity of the second-smallest eigenvalue of nabla a_star(theta), differentiability of its eigenspaces, and finite Fisher information of the noise density.
Required for the van Trees based lower bound; not satisfied by every advertised action set, including Lp balls with p near infinity.
ad hoc to paper Modified matrix Freedman inequality (Lemma 9), a custom adaptation of Tropp's matrix Freedman inequality with the proof omitted.
Central concentration result used to prove the lambda_min(V_T) lower bound with high probability; the exact variant with the stated constants is not proved in the paper.
standard math RLS confidence ellipsoid bound of Abbasi-Yadkori et al. (2011), reproduced as Lemma 11.
Converts a lower bound on lambda_min(V_t) into a high-probability bound on the parameter estimation error.
standard math van Trees inequality (Lemma 14), following Gill-Levit and Ziemann-Sandberg.
Bayesian Cramer-Rao lower bound used to connect regret, Fisher information, and the design matrix in Theorem 15.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds." pith.science (2026). https://pith.science/paper/P536427A

@misc{pith2026241112154,
  author       = {Pith},
  title        = {Pith review of: Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P536427A}},
  note         = {Machine review of arXiv:2411.12154}
}

abstract

We propose and analyze TRAiL (Tangential Randomization in Linear Bandits), a computationally efficient regret-optimal forced exploration algorithm for linear bandits on action sets that are sublevel sets of strongly convex functions. TRAiL estimates the governing parameter of the linear bandit problem through a standard regularized least squares and perturbs the reward-maximizing action corresponding to said point estimate along the tangent plane of the convex compact action set before projecting back to it. Exploiting concentration results for matrix martingales, we prove that TRAiL ensures a $\Omega(\sqrt{T})$ growth in the inference quality, measured via the minimum eigenvalue of the design (regressor) matrix with high-probability over a $T$-length period. We build on this result to obtain an $\mathcal{O}(\sqrt{T} \log(T))$ upper bound on cumulative regret with probability at least $ 1 - 1/T$ over $T$ periods, and compare TRAiL to other popular algorithms for linear bandits. Then, we characterize an $\Omega(\sqrt{T})$ minimax lower bound for any algorithm on the expected regret that covers a wide variety of action/parameter sets and noise processes. Our analysis not only expands the realm of lower-bounds in linear bandits significantly, but as a byproduct, yields a trade-off between regret and inference quality. Specifically, we prove that any algorithm with an $\mathcal{O}(T^\alpha)$ expected regret growth must have an $\Omega(T^{1-\alpha})$ asymptotic growth in expected inference quality. Our experiments on the $L^p$ unit ball as action sets reveal how this relation can be violated, but only in the short-run, before returning to respect the bound asymptotically. In effect, regret-minimizing algorithms must have just the right rate of inference -- too fast or too slow inference will incur sub-optimal regret growth.

Figures

Figures reproduced from arXiv: 2411.12154 by the authors.

**Figure 1.** Visualization of action formation at timet via at = projA a ⋆ (θbt) + ν 2 t µ 2 t for a 2-dimensional convex action set A. The intuition behind TRAiL lies in the geometric properties of the action set that we catalog in Section 4. Choosing an action in a direction allows us to gather information about the reward available in that direction as it reveals how well that action aligns with the governing parameter θ… view at source ↗

**Figure 2.** Comparing FEL, TS, UCB, and TRAiL on a spherical action set in R 10 where the area that lies in one standard deviation from the means of the curves are shaded with their respective colors; (a) shows the effect of DTRAiL on regret, (b)-(c) plots regret with reward error variances of 0.1 and 1, respectively. 8.2 Experiments on Randomly Sampled Ellipsoids For the final experiment, we set εt = 0.1, but significantly exp… view at source ↗

**Figure 3.** Comparing FEL, TS, and TRAiL on randomly selected ellipsoidal action sets where εt ∼ N (0, 0.1); (a), (b) show the regret curves for these algorithms where the the action sets are in R 20 and R 100, respectively, (c) provides a speed comparison in seconds with the dimension of the action space varied between 10 and 200 and averaged over 5 runs with T = 104 . To gauge the computational speeds, we varied the action se… view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: The performance of BayesTS, given in Abeille and Lazaric (2017), on A10 with σ 2 ε = 0.1 and σ 2 θ ⋆ = 0.01, over 20 runs. (a) plots the progress of regret, (b) plots the progress of inference equality, measured via λmin(Vt), (c) plots the log-ratio of regret and infer…

**Figure 5.** Figure 5: Here, λ1 computes the only nonzero eigenvalue of ∇a ⋆ (θ ⋆ ). This quantity captures how well changes in θ ⋆ affect the reward-maximizing action. The smaller it is, the more insensitive the best action becomes to the variation in θ ⋆ . For two actions a1 = a ⋆ (θ ⋆ 1 )…

**Figure 5.** Figure 5: Confidence ellipsoids, defined at Lemma 11 with amax = √ 2, for the progress of BayesTS with θ ⋆ = (1, 1) at ( )T1 = 103 iterations and ( )T2 = 104 iterations are overlaid on the heatmap of λ1(∇a ⋆ (θ ⋆ )). precisely, the major axis of the ellipsoid is larger for A10 t…

**Figure 6.** Figure 6: The geometry of Ap and how it locally behaves similar to a convex set that resembles the sublevel set of a strongly convex function. 35 [PITH_FULL_IMAGE:figures/full_fig_p035_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 30 canonical work pages

[1]

Forced-exploration based algorithms for playing in stochastic linear bandits

Yasin Abbasi-Yadkori, Andr \'a s Antos, and Csaba Szepesv \'a ri. Forced-exploration based algorithms for playing in stochastic linear bandits. In COLT Workshop on On-line Learning with Limited Feedback, volume 92, page 236, 2009

work page 2009
[2]

Improved algorithms for linear stochastic bandits

Yasin Abbasi-yadkori, D\' a vid P\' a l, and Csaba Szepesv\' a ri. Improved algorithms for linear stochastic bandits. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011. URL https://proceedings.neurips.cc/paper_files/paper/2011/fil...

work page 2011
[3]

Linear T hompson sampling revisited

Marc Abeille and Alessandro Lazaric. Linear T hompson sampling revisited. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 176--184. PMLR, 20--22 Apr 2017. URL https://proceedings.mlr.press/v54/abeille17a.html

work page 2017
[4]

Thompson sampling for contextual bandits with linear payoffs

Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In Proceedings of the 30th International Conference on Machine Learning (ICML), pages 127--135. JMLR.org, 2013

work page 2013
[5]

On the Minimax Regret for Linear Bandits in a wide variety of Action Spaces

Debangshu Banerjee and Aditya Gopalan. On the minimax regret for linear bandits in a wide variety of action spaces. ArXiv, abs/2301.03597, 2023. URL https://api.semanticscholar.org/CorpusID:255569807

work page Pith review arXiv 2023
[6]

Exploration in linear bandits with rich action sets and its implications for inference

Debangshu Banerjee, Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Exploration in linear bandits with rich action sets and its implications for inference. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Ma...

work page 2023
[7]

Schapire

Wei Chu, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 15, pages 208--214. JMLR.org, 2011

work page 2011
[8]

Linear bandits in high dimension and recommendation systems

Yash Deshpande and Andrea Montanari. Linear bandits in high dimension and recommendation systems. In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1750--1754, 2012. doi:10.1109/Allerton.2012.6483433

work page arXiv 2012

Show all 40 references

[9]

Gill and Boris Y

Richard D. Gill and Boris Y. Levit. Applications of the van T rees inequality: A B ayesian C ram\' e r- R ao bound. Bernoulli, 1 0 (1/2): 0 59--79, Mar. - Jun. 1995

1995
[10]

Some modified matrix eigenvalue problems

Gene H Golub. Some modified matrix eigenvalue problems. SIAM review, 15 0 (2): 0 318--334, 1973

1973
[11]

Greenewald, Ambuj Tewari, Susan A

Kristjan H. Greenewald, Ambuj Tewari, Susan A. Murphy, and Predrag V. Klasnja. Action centered contextual bandits. Advances in neural information processing systems, 30: 0 5973--5981, 2017. URL https://api.semanticscholar.org/CorpusID:29904027

2017
[12]

Michael Harrison, N

J. Michael Harrison, N. Bora Keskin, and Assaf Zeevi. Bayesian dynamic pricing policies: Learning and earning under a binary prior distribution. Management Science, 58 0 (3): 0 570--586, 2012. URL https://ssrn.com/abstract=2389764

2012
[13]

Jiahao He, Jiheng Zhang, and Rachel Q. Zhang. A reduction from linear contextual bandit lower bounds to estimation lower bounds. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Confe...

2022
[14]

Matrix analysis

Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012

2012
[15]

Following the leader and fast rates in online linear prediction: Curved constraint sets and other regularities

Ruitong Huang, Tor Lattimore, Andr \'a s Gy \"o rgy, and Csaba Szepesv \'a ri. Following the leader and fast rates in online linear prediction: Curved constraint sets and other regularities. Journal of Machine Learning Research, 18 0 (145): 0 1--31, 2017. URL http://jmlr.org/p...

2017
[16]

Perturbation Theory for Linear Operators, volume 132 of Grundlehren der mathematischen Wissenschaften

Tosio Kato. Perturbation Theory for Linear Operators, volume 132 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 1980. ISBN 978-3-540-07558-6

1980
[17]

Cooperative multi-agent bandits with heavy tails

Emilie Kaufmann, Wouter M Koolen, and Aurelien Garivier. Cooperative multi-agent bandits with heavy tails. IEEE Transactions on Information Theory, 67 0 (3): 0 1860--1875, 2021. doi:10.1109/TIT.2020.3035751

2021
[18]

Projection-free optimization on uniformly convex sets

Thomas Kerdreux, Alexandre d'Aspremont, and Sebastian Pokutta. Projection-free optimization on uniformly convex sets. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proc...

2021
[19]

Bora Keskin and Assaf Zeevi

N. Bora Keskin and Assaf Zeevi. Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopic policies. Operations Research, 62 0 (5): 0 1142--1167, 2014. doi:10.1287/opre.2014.1302. Columbia Business School Research Paper No. 14-30, Available at SSRN: https...

2014
[20]

Information directed sampling for linear partial monitoring

Johannes Kirschner, Tor Lattimore, Sarah Filippi, and Matthias Seeger. Information directed sampling for linear partial monitoring. In Advances in Neural Information Processing Systems (NeurIPS), pages 1--12. Curran Associates, Inc., 2020

2020
[21]

Multi-agent multi-armed bandits with limited communication

Pontus Landgren, Vivek Srivastava, and Naomi Ehrich Leonard. Multi-agent multi-armed bandits with limited communication. In Proceedings of the 55th IEEE Conference on Decision and Control (CDC), pages 1792--1797. IEEE, 2016

2016
[22]

Bandit Algorithms

Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020

2020
[23]

Schapire

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, WWW '10, page 661–670, New York, NY, USA, 2010. Association for Computing...

2010
[24]

Linear bandits with polylogarithmic minimax regret

Josep Lumbreras and Marco Tomamichel. Linear bandits with polylogarithmic minimax regret. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 3644--3682. PMLR, 30 ...

2024
[25]

Distributed cooperative decision-making in multiarmed bandits: Frequentist and bayesian algorithms

Daniel Martinez-Rubio, Varun Kanade, and Michal Valko. Distributed cooperative decision-making in multiarmed bandits: Frequentist and bayesian algorithms. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 6142--6149. IEEE, 2019. doi:10.1109/CDC40024.2019.9029256

2019
[26]

Multi-agent thompson sampling for bandit applications with sparse neighbourhood structures

David Martinez-Rubio, Taein Jang, Zaiwei Wang, Alec Koppel, and Alejandro Ribeiro. Multi-agent thompson sampling for bandit applications with sparse neighbourhood structures. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 7647--7656. PMLR, 2021

2021
[27]

Curvature of feasible sets in offline and online optimization

Marco Molinaro. Curvature of feasible sets in offline and online optimization. Mathematics of Operations Research, abs/2002.03213, February 2022. URL https://www.microsoft.com/en-us/research/publication/curvature-of-feasible-sets-in-offline-and-online-optimization/

2002 arXiv
[28]

Dynamical linear bandits

Marco Mussi, Alberto Maria Metelli, and Marcello Restelli. Dynamical linear bandits. In Proceedings of the 37th International Conference on Machine Learning, pages 7156--7166. PMLR, 2020

2020
[29]

Stephen B. Pope. Algorithms for ellipsoids. Technical Report FDA-08-01, Sibley School of Mechanical & Aerospace Engineering, Cornell University, Ithaca, New York, February 2008

2008
[30]

Tsitsiklis

Paat Rusmevichientong and John N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35 0 (2): 0 395--411, 2010. ISSN 0364-765X. doi:10.1287/moor.1100.0446

2010
[31]

Learning to optimize via information-directed sampling

Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sampling. In Proceedings of the 27th Annual Conference on Learning Theory (COLT), pages 1--38. JMLR.org, 2014 a

2014
[32]

Learning to optimize via posterior sampling

Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39 0 (4): 0 1221--1243, 2014 b . ISSN 0364-765X. doi:10.1287/moor.2014.0650

2014
[33]

An information-theoretic analysis of thompson sampling

Daniel Russo and Benjamin Van Roy. An information-theoretic analysis of thompson sampling. Journal of Machine Learning Research (JMLR), 17 0 (1): 0 2442--2471, 2016

2016
[34]

A triangle inequality for cosine similarity

Erich Schubert. A triangle inequality for cosine similarity. In International Conference on Similarity Search and Applications, pages 32--44. Springer, 2021

2021
[35]

Dynamic learning in strategic pricing games

Matt Stern and John R Birge. Dynamic learning in strategic pricing games. Available at SSRN 3579123, 2020

2020
[36]

Freedman's inequality for matrix martingales

Joel Tropp. Freedman's inequality for matrix martingales . Electronic Communications in Probability, 16 0 (none): 0 262 -- 270, 2011. doi:10.1214/ECP.v16-1624. URL https://doi.org/10.1214/ECP.v16-1624

2011 doi
[37]

High-dimensional probability: An introduction with applications in data science, volume 47

Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

2018
[38]

Ruihao Zhu and Eytan H. Modiano. Learning to route efficiently with end-to-end feedback: The value of networked structure. ArXiv, abs/1810.10637, 2018. URL https://api.semanticscholar.org/CorpusID:53030121

2018 arXiv
[39]

On uninformative optimal policies in adaptive lqr with unknown b-matrix

Ingvar Ziemann and Henrik Sandberg. On uninformative optimal policies in adaptive lqr with unknown b-matrix. In Learning for Dynamics and Control, pages 213--226. PMLR, 2021

2021
[40]

Regret lower bounds for learning linear quadratic gaussian systems, 2024

Ingvar Ziemann and Henrik Sandberg. Regret lower bounds for learning linear quadratic gaussian systems, 2024. URL https://arxiv.org/abs/2201.01680

2024 arXiv

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Forced-exploration based algorithms for playing in stochastic linear bandits

Yasin Abbasi-Yadkori, Andr \'a s Antos, and Csaba Szepesv \'a ri. Forced-exploration based algorithms for playing in stochastic linear bandits. In COLT Workshop on On-line Learning with Limited Feedback, volume 92, page 236, 2009

work page 2009

[2] [2]

Improved algorithms for linear stochastic bandits

Yasin Abbasi-yadkori, D\' a vid P\' a l, and Csaba Szepesv\' a ri. Improved algorithms for linear stochastic bandits. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011. URL https://proceedings.neurips.cc/paper_files/paper/2011/fil...

work page 2011

[3] [3]

Linear T hompson sampling revisited

Marc Abeille and Alessandro Lazaric. Linear T hompson sampling revisited. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 176--184. PMLR, 20--22 Apr 2017. URL https://proceedings.mlr.press/v54/abeille17a.html

work page 2017

[4] [4]

Thompson sampling for contextual bandits with linear payoffs

Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In Proceedings of the 30th International Conference on Machine Learning (ICML), pages 127--135. JMLR.org, 2013

work page 2013

[5] [5]

On the Minimax Regret for Linear Bandits in a wide variety of Action Spaces

Debangshu Banerjee and Aditya Gopalan. On the minimax regret for linear bandits in a wide variety of action spaces. ArXiv, abs/2301.03597, 2023. URL https://api.semanticscholar.org/CorpusID:255569807

work page Pith review arXiv 2023

[6] [6]

Exploration in linear bandits with rich action sets and its implications for inference

Debangshu Banerjee, Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Exploration in linear bandits with rich action sets and its implications for inference. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Ma...

work page 2023

[7] [7]

Schapire

Wei Chu, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 15, pages 208--214. JMLR.org, 2011

work page 2011

[8] [8]

Linear bandits in high dimension and recommendation systems

Yash Deshpande and Andrea Montanari. Linear bandits in high dimension and recommendation systems. In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1750--1754, 2012. doi:10.1109/Allerton.2012.6483433

work page arXiv 2012