Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget

Jie Bian; Vincent Y. F. Tan

REVIEW 4 major objections 5 minor 36 references

Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A sampling rule matches the best possible error rate for identifying the best feasible arm in linear bandits under a fixed budget.

desk verdict The problem is new and worth studying, but the main theorems as written do not support the claimed asymptotic optimality: the lower bound has a direction error, the upper bound leans on unverified external lemmas, and the V_T definitions are inconsistent. read the letter →

arxiv 2506.02386 v1 pith:24O2SNJH submitted 2025-06-03 cs.LG cs.AIcs.ITmath.IT

Jie Bian , Vincent Y. F. Tan This is my paper

classification cs.LGcs.AIcs.ITmath.IT

keywords bestfeasiblearmidentificationfixedbudgetlinearbanditsasymptoticoptimalityerrorexponentposteriorsamplingAdaHedgeconstrained

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

This paper closes a gap in fixed-budget best arm identification: for linear bandits where an arm is acceptable only if an unknown linear cost is below a threshold, no earlier algorithm had a proven exponential error rate matching the information-theoretic limit. The authors propose BLFAIPS, a posterior-sampling algorithm that plays a zero-sum game between a min-learner and a max-learner, and prove that its error probability decays as $e^{-T\Gamma}$, where $\Gamma$ is exactly the hardness constant that no sampling rule can beat. If correct, this is the first asymptotically optimal algorithm for constrained best feasible arm identification under a fixed budget, and it unifies a Bayesian and a frequentist expression of the exponent. The claim is supported by experiments on synthetic instances and a MovieLens-based benchmark.

What carries the argument

The load-bearing object is the hardness constant $\Gamma := \max_{w \in \Delta_{\mathcal{X}}} \inf_{(\theta_1,\theta_2) \in \Theta_{z^*}} \frac{1}{2}\left( \frac{\|\theta_1-\theta_r\|^2_{A(w)}}{\sigma^2} + \frac{\|\theta_2-\theta_c\|^2_{A(w)}}{\gamma^2} \right)$, where $A(w)$ is the design matrix of the sampling distribution over training arms. The algorithm mirrors this max-min structure: AdaHedge acts as the max-learner, adaptively choosing sampling weights to maximize distinguishability, while posterior sampling acts as the min-learner, drawing parameters from the posterior truncated to $\Theta_{z^*}$ to simulate the hardest alternative. A G-optimal exploration mixture ensures that the design matrix fills all relevant directions. The proof relates the algorithm's error probability to a Laplace approximation of the posterior ratio, showing that it is asymptotically $e^{-T\Gamma}$.

What would settle it

Simulate BLFAIPS on a small linear instance with known $\theta_r$ and $\theta_c$, and compute the empirical exponent $-\log P(\hat{z}_{\mathrm{out}} \neq z^*)/T$ at large $T$; if it is ever strictly below the hardness $\Gamma$ computed from Theorem 4.1, the central claim is false. The End-of-Optimism instance with a feasibility threshold used in Section 6 is a natural testbed.

Watch

Extended reading notes

Core claim

The paper's central claim is that BLFAIPS attains $\liminf_{T\to\infty} -\frac{1}{T}\log P(\hat{z}_{\mathrm{out}} \neq z^*) \ge \Gamma$ and, together with Theorem 4.1's converse bound $\limsup \le \Gamma$, this makes the algorithm asymptotically optimal. The exponent $\Gamma$ is the maximum over sampling distributions $w$ of the minimum KL divergence to parameters for which the recommended arm is not the best feasible arm; it splits into four terms corresponding to superoptimal-infeasible arms, suboptimal-feasible arms, suboptimal-infeasible arms, and false infeasibility of the true best arm. The paper also proves that the Bayesian posterior form and the frequentist change-of-measure form of this hardness constant are equivalent, and that setting the cost threshold to infinity recovers the unconstrained linear bandit hardness.

Load-bearing premise

The entire upper bound rests on an imported concentration inequality for the posterior truncated to the 'not best feasible arm' parameter set; if that inequality fails for the constrained set, the claimed matching exponent is not established.

Editorial extensions

If this is right

If Theorem 4.3 is correct, no fixed-budget algorithm for this problem can drive the error probability to zero faster than BLFAIPS, settling the asymptotic rate for linear best feasible arm identification.
The four-term decomposition of $\Gamma$ identifies which kind of confusion dominates a given instance: a practitioner can compute each term and see whether the bottleneck is feasibility, reward suboptimality, or the risk of declaring the best arm infeasible.
Replacing exponential weights with AdaHedge removes the doubling trick, so BLFAIPS is anytime and does not need the budget $T$ to be known in advance; the paper demonstrates this advantage empirically against PEPS when $T$ is unknown.
Setting the cost threshold $\tau \to \infty$ recovers the unconstrained linear bandit hardness, showing that the constrained result strictly generalizes the existing theory.
The proven equivalence of the Bayesian and frequentist forms of $\Gamma$ means the exponent can be computed and communicated from either perspective in practice.

Reading between the lines

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

The same min-learner/max-learner game with a modified loss should extend to other constrained identification problems, such as variance-constrained or safety-threshold identification, where the feasible set is defined by a different functional of the parameters.
A testable extension is to sub-Gaussian or heavy-tailed noise: since the exponent is built from KL-type divergences, the Gaussian assumption likely enters only through the posterior form, and one might recover the same $\Gamma$ with a different posterior construction.
The four-term hardness decomposition suggests a diagnostic tool: computing each $f_i(w,z)$ for a problem instance would reveal which arm class limits performance, potentially guiding algorithmic tuning before experiments are run.
Because AdaHedge makes BLFAIPS anytime, an implicit practical consequence is that the algorithm can be stopped at an unknown, externally determined deadline without losing the matching exponent; this is a stronger anytime guarantee than existing tuned Top-Two Thompson sampling variants.

Share X Bluesky LinkedIn Reddit HN

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

Two things you should know about this paper. First, the problem it sets up—fixed-budget linear BAI with an unknown linear cost constraint—is genuinely new and worth working on. Second, the main theorems as written do not support the claimed asymptotic optimality, and the proof issues are load-bearing, not cosmetic.

The authors do real work here. They adapt the PEPS framework to a two-parameter constrained setting, replace exponential weights with AdaHedge to remove the doubling trick, and give a clean unified hardness parameter. The empirical section, though not reproducible without code, shows the algorithm outperforming sensible baselines. Those are legitimate contributions.

But the soft spots are serious. The lower-bound proof in Appendix B computes the probability of correct identification and then treats it as an error probability. The asymptotics as written put P(error) near 1, not exponentially small. A proper exponential lower bound needs a change-of-measure argument over arbitrary algorithms; the proof as given doesn't do that, so the claimed information-theoretic matching is not established. The upper bound in Theorem 4.3 depends on Lemma F.8, which imports Lemma 12 and Corollary 1 from the unpublished Kone et al. preprint without restating them. The stress-test note is right: applicability of Corollary 1 to the possibly non-convex truncation set is not demonstrated, and if that fails the F5 term is not o(1). There is also a definitional inconsistency: Algorithm 1 uses V_t as a cumulative sum, while the theorem statements and the notation table define V_T as an average. That is not a typo; it changes the exponent by a factor of T.

Who should read this? Someone working on constrained BAI or posterior-sampling fixed-budget methods will find the formulation useful and the mistakes instructive. But as a paper claiming to close an open problem, it needs major revision: the lower bound must be redone, the external lemmas must be stated and verified, and the notation fixed. I would not cite it in this form.

It does deserve a serious referee, because the problem is significant and the approach is plausible, but the referee should be asked to check the proofs line by line and the authors should be prepared for heavy revision.

Referee Report

4 major / 5 minor

Summary. The paper considers fixed-budget best feasible arm identification in linear bandits with Gaussian noise, where the learner sequentially pulls training arms to estimate unknown reward and cost parameters, and at the end recommends the feasible test arm with highest estimated reward. The central claim is that the proposed algorithm BLFAIPS, which combines a posterior-sampling 'min-learner' with an AdaHedge 'max-learner', achieves an error probability that decays as exp(-TΓ), and that no algorithm can achieve a faster exponential rate, so the algorithm is asymptotically optimal. The paper provides a proof sketch, a supplementary appendix with detailed arguments, and empirical comparisons on synthetic and real-world instances.

Significance. If the claims were correct, this would be a valuable first asymptotic optimality result for constrained fixed-budget best feasible arm identification in linear bandits, with an attractive game-theoretic formulation and a tuning-free algorithm. The use of AdaHedge to remove the doubling trick, the attempt to unify Bayesian and frequentist rate formulations, and the inclusion of empirical experiments are all positive features. However, the verification is currently incomplete: the rate definition is inconsistent between the algorithm and the analysis, the lower-bound proof does not cover arbitrary algorithms, and the key upper-bound step depends on unstated results from an unpublished preprint.

major comments (4)

[Algorithm 1, Theorem 4.3, Appendix A] The matrix V_T is defined inconsistently. Algorithm 1, line 18, sets V_t = V_{t-1} + X_t X_t^T, so V_T is the cumulative sum (with V_0 = I), while the notation table in Appendix A and the statements of Lemmas 5.5 and 5.6 define V_T := (1/T)(I + Σ_{t=1}^T X_t X_t^T), the average. Theorem 4.3 defines p_{T+1} := N(hat θ^r_{T+1}, σ^2 V_T^{-1}) ⊗ N(hat θ^c_{T+1}, γ^2 V_T^{-1}) | Θ. If V_T is the average, this covariance does not decay with T, the log-density ratio in Lemma 5.5 is of order 1 rather than T, the event E5,∞ as written does not hold, and the Laplace exponent -TΓ is not obtained. If V_T is the sum, then the notation in Lemmas 5.5/5.6 and Theorem 4.3 must be changed. This inconsistency is load-bearing for Theorem 4.3.
[Appendix B (proof of Theorem 4.1)] The claimed lower bound is not proved for arbitrary sampling rules. The proof computes the probability that a sample from the posterior distributions Π^r_T and Π^c_T declares some arm z ≠ z* feasible and better than z*, or declares z* infeasible (Lemmas B.2-B.5). That is exactly the error probability of the posterior-sampling recommendation rule used by the algorithm; it is not a change-of-measure lower bound that applies to any algorithm. No alternative parameter pair (θ1, θ2) ∈ Θ_{z*} is constructed and no divergence between the true and alternative environments is bounded uniformly over algorithms. Hence the statement 'for any sampling rule' in Theorem 4.1 is not established, and the claimed matching lower bound is circular, since the same posterior-sampling rule appears in the upper bound.
[Appendix F.8 (Lemma F.8)] The crucial step F5 = o(1) in the proof of Lemma 5.6 relies on two results imported from Kone et al. [2024] without statement or proof: Corollary 1, used to assert concavity of exp(-Γ1) under η_r ≤ 1/(8L^2 R1^2) and η_c ≤ 1/(8L^2 R2^2), and Lemma 12, used to assert that the sums involving a1, a2 and log E_{p~_t} exp(Γ2) are O(√T log^2 T) with probability 1 - 4/T. These results are not available to the reader, and their hypotheses are not checked for the set Θ_{z*}, which is a union of half-spaces rather than a convex set. Since Lemma F.8 is the only argument turning the Laplace-approximation error into the claimed exponent Γ, Theorem 4.3 is unsupported without these lemmas.
[Section 5 (Lemmas 5.1-5.6)] Theorem 4.3 states 'with probability 1', but the good-event lemmas have failure probabilities that are not summable. Lemma 5.6 gives probability at least 1 - 28/T (and the other lemmas give probabilities of order 1/T or similar); the sum over T of 28/T diverges, so the Borel-Cantelli lemma cannot yield an almost-sure statement. A liminf in probability, or an additional argument, is needed. As written, the 'with probability 1' claim in Theorem 4.3 is not justified.

minor comments (5)

[Algorithm 1, lines 5 and 15] The symbol γ_t denotes both the exploration rate t^{-α} and the cost noise; please use distinct symbols to avoid ambiguity.
[Algorithm 1, line 13] The expression 'λ_t = (1−γ_t)λ_t + γ_tλ_G' is self-referential; introduce a separate symbol, such as \tilde λ_t, for the mixture distribution used to sample X_t.
[Appendix A, notation table] The notation table defines p_{T+1} with η_r^{-1}V_T^{-1} and η_c^{-1}V_T^{-1}, while Algorithm 1 and Theorem 4.3 use σ^2V_T^{-1} and γ^2V_T^{-1}; align these definitions.
[Theorem 4.1] Theorem 4.1 states Θ_r = Θ_c = R^d, which is inconsistent with Assumption 2.1's boundedness of Θ_r and Θ_c; clarify whether the lower bound is intended for unbounded parameters or whether the assumption should be modified.
[Theorem 4.2] The proof of Theorem 4.2 derives the explicit f_i(w,z) expression, but the theorem statement does not display it; state the equivalence explicitly for readability.

Circularity Check

1 steps flagged · score 6.0 of 10

The universal lower bound is derived for the posterior-sampling recommendation rule, making the claimed optimality partially self-definitional.

self definitional [Theorem 4.1 (Section 4.1) and Appendix B; Theorem 4.3 (Section 4.2), Algorithm 1 Lines 26-33]
"Under the environment Θr = Θc = R^d, let Πr_t := N(θ̂r_t, Σr_t), Πc_t := N(θ̂c_t, Σc_t) be the posterior distribution of the unknown θr and θc at time step t, for any sampling rule ... lim sup ... ≤ Γ. ... 1−P(zout≠z∗) ·= max_{z∈Z} {P(µr_n(z)≥µr_n(z∗), µc_n(z)≤τ)·1{z≠z∗}, P(µc_n(z)>τ)·1{z=z∗}}."

The lower bound is proved by drawing µr_n and µc_n from the posterior and asking whether the posterior draw fails to be optimal/feasible; this is precisely the posterior-sampling recommendation used by BLFAIPS in Lines 26-33, where p_{T+1} := N(θ̂r_{T+1}, σ²V_T^{-1}) ⊗ N(θ̂c_{T+1}, γ²V_T^{-1})|Θ. Theorem 4.3 then guarantees an exponent Γ for that same posterior draw. Thus the 'information-theoretic lower bound' as proved only constrains the posterior-sampling recommender, not arbitrary strategies; the statement 'no strategy can achieve faster exponential decay rate' is not an independent first-principles limit. The matching lower and upper bounds describe the same decision rule, so the optimality claim reduces in part to the algorithm's own construction.

full rationale

The paper's upper-bound analysis (Sections 5 and F) is substantial and independent: it proves concentration, AdaHedge regret, G-optimal exploration, and the Laplace approximation that turns the posterior integral into exp(−TΓ). No load-bearing self-citation chain was found; the Kone et al. [2024] lemmas used in Lemma F.8 are external, not author-self-citations, though they are unverified imports and a correctness risk. The circularity is concentrated in the claimed matching: Theorem 4.1's proof evaluates the error of a posterior-sampling decision rule, and BLFAIPS's final recommendation is exactly such a rule, so the 'optimality' claim that no strategy can beat Γ is not established by an algorithm-independent change-of-measure argument. This makes the central asymptotic-optimality claim partially self-definitional, while leaving the non-trivial convergence analysis intact. The score of 6 reflects partial circularity of the headline optimality claim, not full equivalence of the derivation to its inputs.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claim depends on the domain assumptions (bounded parameters, unique best arm, Gaussian noise), on a set of external lemmas from Kone et al. [2024] that are not proved here, and on hand-chosen algorithm constants (alpha and eta). No new physical entities are introduced.

free parameters (2)

alpha (exploration shrinking rate) = 1/4
Set to 1/4 in Algorithm 1; the proof in Lemma F.5 requires gamma_t = t^{-1/4} to make F2,3 = o(1). This is a hand-chosen constant, not fitted to data.
eta (posterior sampling learning rate) = min(sigma^2/(8L^2 R1^2), gamma^2/(8L^2 R2^2))
Chosen to ensure concavity of exp(-Gamma1) in Lemma F.8 via Corollary 1 of Kone et al. [2024]; depends on known bounds.

assumptions (5)

domain assumption Assumption 2.1: Theta_r and Theta_c are bounded and closed sets
Invoked throughout the upper-bound analysis to ensure concentration of ridge estimates (Lemmas 5.1 and 5.2) and boundedness of losses for AdaHedge.
domain assumption Assumption 2.3: the best feasible arm is unique and span(Z) is a subset of span(X)
Required for Lemma 5.4, which shows the empirical best feasible arm equals the true one after O(log T) rounds.
domain assumption Gaussian noise on reward and cost observations
The posterior is Gaussian and the lower-bound proof uses Gaussian tail bounds (Lemma B.1).
ad hoc to paper External lemmas from Kone et al. [2024] (Lemma 12 and Corollary 1)
Lemma F.8 invokes these to control the log-partition function of the truncated posterior over Theta_zhat; they are not proved in this paper.
standard math Laplace approximation (Lemma G.3)
Used to convert the posterior integral to an exponential rate; requires the exponent to have a unique infimum.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget." pith.science (2026). https://pith.science/paper/24O2SNJH

@misc{pith2026250602386,
  author       = {Pith},
  title        = {Pith review of: Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/24O2SNJH}},
  note         = {Machine review of arXiv:2506.02386}
}

abstract

The challenge of identifying the best feasible arm within a fixed budget has attracted considerable interest in recent years. However, a notable gap remains in the literature: the exact exponential rate at which the error probability approaches zero has yet to be established, even in the relatively simple setting of $K$-armed bandits with Gaussian noise. In this paper, we address this gap by examining the problem within the context of linear bandits. We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability. Remarkably, the decay rate -- characterized by the exponent -- matches the theoretical lower bound derived using information-theoretic principles. Our approach leverages a posterior sampling framework embedded within a game-based sampling rule involving a min-learner and a max-learner. This strategy shares its foundations with Thompson sampling, but is specifically tailored to optimize the identification process under fixed-budget constraints. Furthermore, we validate the effectiveness of our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity. The results corroborate our theoretical findings and demonstrate that our method outperforms several benchmark algorithms in terms of both accuracy and efficiency.

Figures

Figures reproduced from arXiv: 2506.02386 by the authors.

**Figure 3.** d = 2, K = 50 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

**Figure 1.** α = 0.1 The experimental results, as illustrated by the plots, demonstrate that our proposed algorithm, BLFAIPS, consistently outperforms alternative approaches, including the constrained versions of Linear Thompson Sampling and Linear β-Top-two Thompson Sampling. This performance advantage persists even when the β parameter is fine-tuned to match the true allocation rate of the given instance. 6.2 RANDOM INSTANC… view at source ↗

Figures from the paper (6 more)

**Figure 6.** Figure 6: Comparison of accuracies of various algorithms [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]

**Figure 5.** Figure 5: Comparison of BLFAIPS to PEPS for unknown [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]

**Figure 7.** Figure 7: α = 0.2 [PITH_FULL_IMAGE:figures/full_fig_p035_7.png]

**Figure 8.** Figure 8: α = 0.3 [PITH_FULL_IMAGE:figures/full_fig_p035_8.png]

**Figure 9.** Figure 9: d = 2, K = 20 [PITH_FULL_IMAGE:figures/full_fig_p036_9.png]

**Figure 10.** Figure 10: d = 20, K = 20 [PITH_FULL_IMAGE:figures/full_fig_p036_10.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

36 extracted references · 28 canonical work pages

[1]

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. Advances in Neural Information Processing Systems, 24, 2011

work page 2011
[2]

Thompson sampling for contextual bandits with linear payoffs

Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pages 127--135. PMLR, 2013

work page 2013
[3]

Linear stochastic bandits under safety constraints

Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. Advances in Neural Information Processing Systems, 32, 2019

work page 2019
[4]

Best arm identification in multi-armed bandits

Jean-Yves Audibert and S \'e bastien Bubeck. Best arm identification in multi-armed bandits. In Proc. of 23rd Conference on Learning Theory, page 13, 2010

work page 2010
[5]

Finite-time analysis of the multiarmed bandit problem

Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47: 0 235--256, 2002

work page 2002
[6]

Fixed-Budget Best-Arm Identification in Structured Bandits

Mohammad Javad Azizi, Branislav Kveton, and Mohammad Ghavamzadeh. Fixed-budget best-arm identification in structured bandits. arXiv preprint arXiv:2106.04763, 2021

work page Pith review arXiv 2021
[7]

A survey on practical applications of multi-armed and contextual bandits

Djallel Bouneffouf and Irina Rish. A survey on practical applications of multi-armed and contextual bandits. arXiv preprint arXiv:1904.10040, 2019

arXiv 1904
[8]

Active learning with safety constraints

Romain Camilleri et al. Active learning with safety constraints. Advances in Neural Information Processing Systems, 35: 0 33201--33214, 2022

work page 2022

Show all 36 references

[9]

Follow the leader if you can, hedge if you must

Steven De Rooij, Tim Van Erven, Peter D Gr \"u nwald, and Wouter M Koolen. Follow the leader if you can, hedge if you must. The Journal of Machine Learning Research, 15 0 (1): 0 1281--1316, 2014

2014
[10]

Constrained pure exploration multi-armed bandits with a fixed budget

Fathima Zarin Faizal and Jayakrishnan Nair. Constrained pure exploration multi-armed bandits with a fixed budget. arXiv preprint arXiv:2211.14768, 2022

2022 arXiv
[11]

Best arm identification: A unified approach to fixed budget and fixed confidence

Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. Advances in Neural Information Processing Systems, 25, 2012

2012
[12]

Yunlong Hou, Vincent Y. F. Tan, and Zixin Zhong. Almost optimal variance-constrained best arm identification. IEEE Transactions on Information Theory, 69 0 (4): 0 2603--2634, 2023

2023
[13]

Optimal best-arm identification in linear bandits

Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 33: 0 10007--10017, 2020

2020
[14]

PAC subset selection in stochastic multi-armed bandits

Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. PAC subset selection in stochastic multi-armed bandits. In International Conference on Machine Learning, volume 12, pages 655--662, 2012

2012
[15]

Almost optimal exploration in multi-armed bandits

Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238--1246. PMLR, 2013

2013
[16]

Feasible arm identification

Julian Katz-Samuels and Clay Scott. Feasible arm identification. In International Conference on Machine Learning, pages 2535--2543. PMLR, 2018

2018
[17]

Top feasible arm identification

Julian Katz-Samuels and Clayton Scott. Top feasible arm identification. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1593--1601. PMLR, 2019

2019
[18]

Minimax optimal algorithms for fixed-budget best arm identification

Junpei Komiyama, Taira Tsuchiya, and Junya Honda. Minimax optimal algorithms for fixed-budget best arm identification. Advances in Neural Information Processing Systems, 35: 0 10393--10404, 2022

2022
[19]

Pareto set identification with posterior sampling

Cyrille Kone, Marc Jourdan, and Emilie Kaufmann. Pareto set identification with posterior sampling. arXiv preprint arXiv:2411.04939, 2024

2024 arXiv
[20]

Algorithms for multi-armed bandit problems

Volodymyr Kuleshov and Doina Precup. Algorithms for multi-armed bandit problems. arXiv preprint arXiv:1402.6028, 2014

2014 arXiv
[21]

Polynomial-time algorithms for multiple-arm identification with full-bandit feedback

Yuko Kuroki, Liyuan Xu, Atsushi Miyauchi, Junya Honda, and Masashi Sugiyama. Polynomial-time algorithms for multiple-arm identification with full-bandit feedback. Neural Computation, 32 0 (9): 0 1733--1773, 2020

2020
[22]

Striatum: A contextual bandit library

NTU Computational Lab. Striatum: A contextual bandit library. https://github.com/ntucllab/striatum, 2017. Accessed: 2025-06-02

2017
[23]

The end of optimism? an asymptotic analysis of finite-armed linear bandits

Tor Lattimore and Csaba Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. In Artificial Intelligence and Statistics, pages 728--737. PMLR, 2017

2017
[24]

Bandit Algorithms

Tor Lattimore and Csaba Szepesv \'a ri. Bandit Algorithms. Cambridge University Press, 2020

2020
[25]

Optimal exploration is no harder than Thompson sampling

Zhaoqi Li, Kevin Jamieson, and Lalit Jain. Optimal exploration is no harder than Thompson sampling. In International Conference on Artificial Intelligence and Statistics, pages 1684--1692. PMLR, 2024

2024
[26]

The racing algorithm: Model selection for lazy learners

Oden Maron and Andrew W Moore. The racing algorithm: Model selection for lazy learners. Artificial Intelligence Review, 11: 0 193--225, 1997

1997
[27]

Safe linear Thompson sampling with side information

Ahmadreza Moradipari, Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Safe linear Thompson sampling with side information. IEEE Transactions on Signal Processing, 69: 0 3755--3767, 2021

2021
[28]

Contextual bandits with stage-wise constraints

Aldo Pacchiano, Mohammad Ghavamzadeh, and Peter Bartlett. Contextual bandits with stage-wise constraints. arXiv preprint arXiv:2401.08016, 2024

2024 arXiv
[29]

Simple Bayesian algorithms for best arm identification

Daniel Russo. Simple Bayesian algorithms for best arm identification. In Conference on Learning Theory, pages 1417--1418. PMLR, 2016

2016
[30]

Price of safety in linear best arm identification

Xuedong Shang, Igor Colin, Merwan Barlier, and Hamza Cherkaoui. Price of safety in linear best arm identification. arXiv preprint arXiv:2309.08709, 2023

2023 arXiv
[31]

Pure exploration for constrained best mixed arm identification with a fixed budget

Dengwang Tang, Rahul Jain, Ashutosh Nayyar, and Pierluigi Nuzzo. Pure exploration for constrained best mixed arm identification with a fixed budget. arXiv preprint arXiv:2405.15090, 2024

2024 arXiv
[32]

Thompson

William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25 0 (3/4): 0 285--294, 1933. ISSN 00063444. URL http://www.jstor.org/stable/2332286

1933
[33]

Best arm identification with safety constraints

Zhenlin Wang, Andrew J Wagenmaker, and Kevin Jamieson. Best arm identification with safety constraints. In International Conference on Artificial Intelligence and Statistics, pages 9114--9146. PMLR, 2022

2022
[34]

Minimax optimal fixed-budget best arm identification in linear bandits

Junwen Yang and Vincent Tan. Minimax optimal fixed-budget best arm identification in linear bandits. Advances in Neural Information Processing Systems, 35: 0 12253--12266, 2022

2022
[35]

Stochastically constrained best arm identification with Thompson sampling

Le Yang, Siyang Gao, Cheng Li, and Yi Wang. Stochastically constrained best arm identification with Thompson sampling. Automatica, 176: 0 112223, Jun 2025

2025
[36]

On kernelized multi-armed bandits with constraints

Xingyu Zhou and Bo Ji. On kernelized multi-armed bandits with constraints. Advances in Neural Information Processing Systems, 35: 0 14--26, 2022

2022

Pith tools

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

[1] [1]

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. Advances in Neural Information Processing Systems, 24, 2011

work page 2011

[2] [2]

Thompson sampling for contextual bandits with linear payoffs

Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pages 127--135. PMLR, 2013

work page 2013

[3] [3]

Linear stochastic bandits under safety constraints

Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. Advances in Neural Information Processing Systems, 32, 2019

work page 2019

[4] [4]

Best arm identification in multi-armed bandits

Jean-Yves Audibert and S \'e bastien Bubeck. Best arm identification in multi-armed bandits. In Proc. of 23rd Conference on Learning Theory, page 13, 2010

work page 2010

[5] [5]

Finite-time analysis of the multiarmed bandit problem

Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47: 0 235--256, 2002

work page 2002

[6] [6]

Fixed-Budget Best-Arm Identification in Structured Bandits

Mohammad Javad Azizi, Branislav Kveton, and Mohammad Ghavamzadeh. Fixed-budget best-arm identification in structured bandits. arXiv preprint arXiv:2106.04763, 2021

work page Pith review arXiv 2021

[7] [7]

A survey on practical applications of multi-armed and contextual bandits

Djallel Bouneffouf and Irina Rish. A survey on practical applications of multi-armed and contextual bandits. arXiv preprint arXiv:1904.10040, 2019

arXiv 1904

[8] [8]

Active learning with safety constraints

Romain Camilleri et al. Active learning with safety constraints. Advances in Neural Information Processing Systems, 35: 0 33201--33214, 2022

work page 2022