Pith. sign in

REVIEW 2 major objections 5 minor 52 references

Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts

T0 review · 2 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 Bayesian incentive-compatible bandit algorithm can learn every direction of the unit ball in polynomially many samples, not exponentially many.

desk verdict Polynomial-sample BIC exploration for the unit ball: the barrier in Sellke's lower bound is geometric; the proof holds, with oracle and polish caveats. read the letter →

arxiv 2506.01685 v1 pith:7XNI5N4S submitted 2025-06-02 cs.GT cs.LG

Benjamin Schiffer , Mark Sellke This is my paper
classification cs.GTcs.LG
keywords incentivizedexplorationlinearbanditsBayesianincentivecompatibilityThompsonsamplingspectralsamplecomplexityunitballgeometry
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

The paper asks whether a platform can explore a high-dimensional linear bandit when every recommendation must be justified to a self-interested agent who only cares about the current payoff. It shows that the deciding factor is the geometry of the action set: when the actions fill the Euclidean unit ball, incentive compatibility does not force an exponential exploration cost. The main result is a Bayesian incentive-compatible (BIC) algorithm that achieves $\lambda$-bar-spectral exploration in sample complexity $\lambda$-bar(d/c_v + c_d)^{O(1)} log(1/epsilon_d), polynomial in the dimension and in the reciprocal of the prior's non-degeneracy parameters. Because such spectral exploration makes Thompson sampling (approximately) BIC thereafter, the algorithm can be composed into an end-to-end learner whose regret matches the standard Thompson-sampling benchmark up to polynomial pre-constants. This matters because it draws a clear geometric line between the exponential hardness known for polytope action sets and smooth action sets like the unit ball.

What carries the argument

The central object is the map Exploit(psi, v), which returns the normalized posterior mean E[ell*|psi]/||E[ell*|psi]||; Lemma 2.1 guarantees this action is BIC whenever psi depends only on the past and independent randomness. The engine is the exponential-growth subroutine (Algorithm 6): with the unexplored subspace S_perp and a BIC action a, it averages L rewards to form a signal R of the form L||P_{S_perp}(a)||<x, ell*> + W, where x is the unit vector in S_perp; Lemmas A.2 and A.3 show that conditioning on the sign of R at least doubles ||P_{S_perp}(E[ell*|sign(R)])|| relative to ||P_{S_perp}(a)||. The initial-exploration subroutine (Algorithm 5) supplies the first such action by constructing a Bernoulli event with probability $\Omega$(epsilon_d) under which the posterior mean on the already-explored subspace is zero, so the recommended action lies in S_perp with magnitude at least c_L $c_v^{{2.5}}$ epsilon_d c_d. Finally, Lemma 2.3 is a linear-algebra push lemma: adding a rank-one update u tensor u with ||P_{S_perp}(u)||^2 >= epsilon increases the sum of the small eigenvalues of the design matrix by at least epsilon/2, which caps the number of outer iterations at O($d^{4}$/$lambda^{3}$).

What would settle it

A direct falsifier is a prior satisfying Assumption 1.2 on the unit ball for which no BIC algorithm achieves lambda-spectral exploration in poly(d) samples; if such a prior exists, Theorem 1.3 is false. A computational check is to simulate Algorithm 6 with d = 2, known first coordinate, and Gaussian measurement noise, and verify that ||P_{S_perp}(b)||/||P_{S_perp}(a)|| >= 2 whenever the parameters satisfy the signal-to-noise condition (19); a ratio below 2 in any admissible configuration would break Proposition 3.3.

Watch

Extended reading notes

Core claim

The paper proves Theorem 1.3: under Assumption 1.2, there exists a BIC algorithm (Algorithm 4) that almost surely achieves $\lambda$-bar-spectral exploration in sample complexity $\lambda$-bar(d/c_v + c_d)^{O(1)} log(1/epsilon_d), where Assumption 1.2 asks that the prior not be confined to any half-space, have covariance at least c_v in every direction, and be sub-gaussian with constant K. The algorithm proceeds by repeatedly finding a BIC action with small but polynomial-sized projection onto the unexplored subspace, doubling that projection by conditioning on the sign of a de-noised reward signal, and then playing the resulting action for a polynomial number of steps to push all eigenvalues of the empirical design matrix above $\lambda$. The doubling is possible because on the unit ball the Bayesian-optimal action given a signal is the normalized posterior mean, and conditioning on the sign of a noisy reward inflates the posterior mean in the unexplored direction by at least a factor of two. The paper also shows that the initial exploration phase can be run with probability only epsilon_d, that each outer loop strictly raises the small eigenvalues by a constant (Lemma 2.3), and that the total number of rounds is O($d^{4}$/$lambda^{3}$).

Load-bearing premise

The whole polynomial bound rests on one amplification property: conditioning on the sign of a noisy reward in an unexplored direction at least doubles the posterior's push in that direction, which holds on the unit ball only for Gaussian noise and only when the signal-to-noise ratio is tuned so that $\lambda$ = $\Omega$(c_v/d); if the doubling factor ever dropped below 2, the inner growth loop would require exponentially many rounds.

Editorial extensions

If this is right

  • For any r-regular prior, the initial exploration runs in poly(d, 1/r, 1/epsilon) steps, after which Thompson sampling is epsilon-BIC with regret poly(d, 1/r, 1/epsilon) + O-tilde(d sqrt(T)) in the Bayesian sense and O-tilde(d^{3/2} sqrt(T)) in the frequentist sense.
  • The exploration cost is independent of the time horizon T, so the incentive constraint adds only a polynomial pre-constant to the regret rather than an exponential factor.
  • The exponential lower bound shown for polytope action sets does not transfer to the unit ball, so the smoothness of the action space, not the dimension alone, governs whether BIC exploration is tractable.
  • If Assumption 1.2's half-space condition is dropped, the algorithm still provides epsilon-BIC spectral exploration and can be combined with Thompson sampling, giving end-to-end guarantees under weaker assumptions.

Reading between the lines

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

  • The doubling mechanism suggests that the polynomial bound extends to any smooth, strictly convex body whose arg-max map is expansive; an ellipsoid or a C^2 perturbation of the ball is a natural next test case.
  • Because the growth-step analysis uses the Mills-ratio expansion of Gaussian noise, a plausible generalization is to heavier-tailed noise via interval-based conditioning rather than sign-based conditioning.
  • Lemma 2.3, a rank-one eigenvalue push lemma, may be useful outside bandits in any sequential design problem where one must raise the smallest eigenvalue of a moment matrix with few samples.
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.

Referee Report

2 major / 5 minor

Summary. The paper studies incentivized exploration in linear bandits with actions in the Euclidean unit ball. It proposes a Bayesian incentive-compatible (BIC) algorithm (Algorithm 4) that first plays a fixed action, then iteratively discovers unexplored directions using two subroutines: InitialExploration produces a BIC action with a small nonzero projection onto the currently unexplored subspace, and ExponentialGrowth doubles that projection using the curvature or expansiveness of the argmax map on the ball. The main result (Theorem 1.3 / Theorem 3.4) is a polynomial sample-complexity bound for lambda-spectral exploration under a non-degeneracy and sub-Gaussian prior assumption, which can be combined with Sellke's Thompson-sampling analysis to obtain an end-to-end epsilon-BIC algorithm with near-optimal regret for r-regular priors.

Significance. If the main theorem is correct in its current form, this is a significant positive result: it removes the exponential barrier exhibited for polytope action sets in [Sel23] and identifies smoothness of the action set as the key geometric property that enables BIC exploration. The proof architecture is transparent and modular, with all auxiliary lemmas proved in the appendices; the contrast between the unit ball and polytopes, via expansiveness of ell* -> arg max vs. plateaus at corners, is conceptually illuminating. The paper also makes explicit the signal-to-noise condition (Equation (19)) that forces lambda = Omega(c_v/d), which is a useful check on where the polynomial guarantee operates. However, because two load-bearing propositions have proof gaps identified below, I cannot certify the theorem as stated.

major comments (2)
  1. [Appendix I (Proof of Proposition 3.2)] The proof omits the normalization in Exploit. By Lemma 2.1 and Algorithm 5, the returned action is a = E[ell* | 1_{R>0}] / ||E[ell* | 1_{R>0}]||, not the unnormalized conditional expectation. The displayed equality |<A,a>| = |<A, E[ell* | 1_{R>0}]>| is therefore missing a factor of 1/||E[ell* | 1_{R>0}]||. The proof supplies no upper bound on this denominator, so the claimed lower bound ||P_{S^perp}(a)|| >= c_LA.1 c_v^{2.5} epsilon_d c_d / (16(K sqrt(pi)+1)) does not follow as written. Since Proposition 3.2 provides the starting magnitude for the doubling loop, this gap is load-bearing for Theorem 3.4. A repair using a sub-Gaussian norm bound for conditional expectations would introduce an additional dimension factor but would probably preserve the polynomial conclusion; as written, however, the proposition is not proved. Relatedly, the application of Lemma A.1 requires the mixing Bernoulli in Algorithm 5 to be independent of X = <ell*, A>; that Bernoulli depends on z(hat y) and hence on past rewards, and conditional on the exploration event X has a positive posterior mean, so the hypotheses of Lemma A.1 are not directly verified.
  2. [Algorithm 6 and Appendix J (Proof of Proposition 3.3)] The definition of R on Line 7 of Algorithm 6 uses q^{t'}_k for t' = t, ..., t+L-1, but the arrays passed to Algorithm 6 are only defined for t' in [0, kappa) (Algorithm 4, Lines 18-21). Since action a is being played during the current block, there is no reward from v_k at current time t' that could serve as q^{t'}_k. Consequently the identity R = L <P_{S^perp}(a), ell*> + W in Equation (18), and hence the SNR check in Equation (19) and the factor-2 doubling bound, are not established for the algorithm as written. The routine appears repairable, for example by replacing the sum over q^{t'}_k with a block average of the kappa stored rewards and adjusting the noise variance accordingly, but this is a substantive revision to Algorithm 6 and its proof, not a typographical detail.
minor comments (5)
  1. [Appendix K (Proof of Theorem 3.4)] The text says 'after 400d^4/lambda^2 + d applications of Lemma 2.3', but the immediately following sentence and the arithmetic require 400d^4/lambda^3 + d; the exponent of lambda appears to be a typo.
  2. [Appendix E (Proof of Lemma 2.3)] The proof does not explicitly handle the case ell = 0, where the quantities lambda_ell used in the displayed inequalities are undefined; the case is trivial because the relevant sums are empty, but it should be stated for completeness.
  3. [Algorithm 5, Line 7] The phrase 'valid probabilities' is terse: the reader must verify that f(z(hat y)) >= epsilon_d c_d / (16(K sqrt(pi)+1)) from Lemma 2.2, so that the conditional probability c/f(z(hat y)) is at most 1; this verification should be spelled out in the text or in a remark.
  4. [Algorithms 5 and 6] The notation q^{t'}_k is used with t' ranging over stored offsets (0 <= t' < kappa) in some places and over global time in others; even once the indexing issue in Major Comment 2 is fixed, the two roles of t' should be denoted differently to avoid confusion.
  5. [Proof of Proposition 3.2] In the definition of A, the denominator ||E[ell* | Psi=1]|| is typeset with a subscript 2 that should be a norm; this is cosmetic but confusing.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sample-complexity theorem is proved from auxiliary lemmas that are themselves proven in the appendices, and the self-citations are baselines or explicitly labelled combination partners rather than premises.

full rationale

Theorem 1.3 is derived in Theorem 3.4 from Proposition 3.2 (InitialExploration yields a BIC action with Omega(epsilon_d c_d) projection), Proposition 3.3 (ExponentialGrowth doubles the projection), and Lemma 2.3 (eigenvalue progress). Each of these is proved from Lemmas A.1-A.5, which are proved in Appendices G, H, and F from Gaussian/sub-Gaussian assumptions and Assumption 1.2. The probability-space construction in Lemma 2.2 is proved in Appendix G, not assumed. The value of lambda is defined using constants from Lemmas A.2 and A.3, but those lemmas are independently proved; lambda is not fitted to the final bound. Citations to [Sel23], [SS23], and [BS22] are used as baselines, as the source of the contrasting polytope lower bound, and in Section 4 as an explicitly labelled combination partner for end-to-end Thompson-sampling regret; they are not premises of the main sample-complexity derivation. No equation in the proof chain reduces to its own conclusion, and no fitted parameter is renamed as a prediction.

Assumptions & free parameters 4 free parameters · 7 assumptions · 0 invented entities

The central claim rests on the three conditions of Assumption 1.2 plus the Gaussian noise model, all stated as assumptions on the problem. The algorithm's own constants (lambda, kappa, L and the lemma constants) are hand-chosen to make the proof close; the algorithm needs to know c_d, epsilon_d, c_v, K (for kappa and Algorithm 5's Line 7), so the guarantee is parameterized by the prior's regularity constants. No new physical or mathematical entities are postulated: the event E and filter f of Lemma 2.2 are internal constructions with existence proofs. The self-cited prior results [Sel23, SS23] enter as baseline, definitional, or explicitly-labeled combination partners, not as assumed conclusions.

free parameters (4)
  • lambda (spectral exploration threshold) = Omega(c_v/d); defined as min(1, min(delta_LA.2, delta_LA.3, 1/c_LA.3)^2 (c_v/sqrt(8pi))^2 / (4d(K sqrt(pi)+1)^2))
    Hand-chosen so that the signal-to-noise condition of Equation (19) holds, i.e., L ||P_{S_perp}(a)||/sigma_W <= min(delta_LA.2, delta_LA.3, 1/c_LA.3), which Lemmas A.2 and A.3 need for the factor-2 amplification. It enters the final bound as 1/lambda^4.
  • kappa (per-block sample count) = max(1/(lambda c_LA.4), 4d(K sqrt(pi)+1)(1+1/lambda)/(c_v^2/8pi))
    Number of reward samples recorded for each explored action; chosen so the y_hat estimates in Algorithm 5 have variance c_LA.4 lambda/lambda_l <= c_LA.4, matching Lemma 3.1's requirement for Lemma A.4.
  • L (ExponentialGrowth block length) = 4d(E[ell*_1]+1)^2 (1 + sum_k c_k^2)/c_LA.2^2
    Number of samples for which the current action a is played in Algorithm 6. Chosen so that the average-reward signal R has the signal-to-noise ratio needed for the factor-2 amplification in Proposition 3.3. As written, L is not bounded above by kappa (only by kappa times a factor (K sqrt(pi)+1)), causing the indexing gap flagged in red_flags.
  • Universal proof constants (c_LA.1, c_LA.2, c_LA.3, delta_LA.2, delta_LA.3, c_LA.4, constants in Lemmas A.1-A.4 and… = Explicit small constants fixed by the proofs (e.g., c_LA.2 = c_v/sqrt(8pi), c_LA.4 = c_d^2/(32 log(4/epsilon_d)))
    Chosen by hand so that the inequalities in the appendix proofs close; they depend on K, c_v, c_d and are not fitted to any data.
assumptions (7)
  • domain assumption Prior is not confined to any half-space: min_{||v||=1} Pr(<v, ell*> >= c_d) >= epsilon_d (Assumption 1.2(1))
    Necessary for BIC exploration (Appendix B shows violation makes A(t) = e_1 forever); it sets the epsilon_d scale that the algorithm pays for only logarithmically.
  • domain assumption Non-degenerate covariance: min_{||v||=1} Var(<v, ell*>) >= c_v (Assumption 1.2(2))
    Needed for Lemma A.1's sigma_X^5 lower bound and for the c_v factors in Propositions 3.2 and 3.3; Appendix B gives a necessity example.
  • domain assumption Sub-gaussian prior: max_{||v||=1} P(|<v, ell*>| >= t) <= 2e^{-t^2/K^2} (Assumption 1.2(3))
    Used for moment bounds (Equations 3-4), in Lemmas A.1 and A.3, and to bound E[ell*_1] <= K sqrt(pi) in Propositions 3.2 and 3.3.
  • domain assumption Reward noise is Gaussian: w_t ~ N(0,1), i.i.d.
    The Taylor and Mills-ratio expansions in Lemmas A.2 and A.3 (Appendices G.1-G.2) and the exact constants delta_LA.2, c_LA.3 are specific to Gaussian noise; the model is stated in Section 1.1.
  • standard math Revelation principle: restricting to BIC recommendations is without loss when agents are homogeneous rational Bayesians (Myerson 1986)
    Underpins Definition 1.1 and Lemma 2.1's characterization of the BIC action as the normalized posterior mean.
  • domain assumption After lambda-spectral exploration, Thompson sampling is epsilon-BIC and low-regret ([Sel23, Thm 3.5], [DVR18], [AG13])
    Used only in Section 4 for the end-to-end regret claim, not for Theorem 1.3; explicitly labeled as a combination with prior work.
  • standard math Standard log-concave facts: concentration (Fact M.1, [DCWY19, DM19]), covariance sandwich (Fact M.2, [CP23]), projection invariance (Fact M.3, [SW14]); Mills-ratio bound [Gor41]
    Used in Appendix M to verify Assumption 1.2 for log-concave priors (Proposition 1.5), an illustrative application rather than the main theorem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts." pith.science (2026). https://pith.science/paper/7XNI5N4S

@misc{pith2026250601685,
  author       = {Pith},
  title        = {Pith review of: Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7XNI5N4S}},
  note         = {Machine review of arXiv:2506.01685}
}
read the original abstract

In the incentivized exploration model, a principal aims to explore and learn over time by interacting with a sequence of self-interested agents. It has been recently understood that the main challenge in designing incentive-compatible algorithms for this problem is to gather a moderate amount of initial data, after which one can obtain near-optimal regret via posterior sampling. With high-dimensional contexts, however, this \emph{initial exploration} phase requires exponential sample complexity in some cases, which prevents efficient learning unless initial data can be acquired exogenously. We show that these barriers to exploration disappear under mild geometric conditions on the set of available actions, in which case incentive-compatibility does not preclude regret-optimality. Namely, we consider the linear bandit model with actions in the Euclidean unit ball, and give an incentive-compatible exploration algorithm with sample complexity that scales polynomially with the dimension and other parameters.

Figures

Figures reproduced from arXiv: 2506.01685 by the authors.

Figure 1
Figure 1. Diagram illustrating exponentially growing exploration. First, we have a BIC [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

52 extracted references · 51 canonical work pages

  1. [1]

    Agrawal and N

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

    work page 2013

  2. [2]

    Agrawal and N

    S. Agrawal and N. Goyal. Near-optimal regret bounds for Thompson Sampling . Journal of the ACM (JACM) , 64(5):1--24, 2017

    work page 2017

  3. [3]

    G. W. Anderson, A. Guionnet, and O. Zeitouni. An Introduction to Random Matrices . Number 118. Cambridge university press, 2010

    work page 2010

  4. [4]

    J. D. Abernethy, E. Hazan, and A. Rakhlin. Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization . In COLT , pages 263--274. Citeseer, 2008

    work page 2008

  5. [5]

    Agrawal and T

    P. Agrawal and T. Tulabandhula. Incentivising exploration and recommendations for contextual bandits with payments. In Multi-Agent Systems and Agreement Technologies: 17th European Conference, EUMAS 2020, and 7th International Conference, AT 2020, Thessaloniki, Greece, September 14-15, 2020, Revised Selected Papers 17 , pages 159--170. Springer, 2020

    work page 2020

  6. [6]

    Bubeck, N

    S. Bubeck, N. Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning , 5(1):1--122, 2012

    work page 2012

  7. [7]

    Bubeck, N

    S. Bubeck, N. Cesa-Bianchi, and S. M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Conference on Learning Theory , pages 41--1. JMLR Workshop and Conference Proceedings, 2012

    work page 2012

  8. [8]

    Bubeck, M

    S. Bubeck, M. Cohen, and Y. Li. Sparsity, variance and curvature in multi-armed bandits. In Algorithmic Learning Theory , pages 111--127. PMLR, 2018

    work page 2018

Show all 52 references
  1. [9]

    Bubeck and R

    S. Bubeck and R. Eldan. The entropic barrier: Exponential families, log-concave geometry, and self-concordance . Mathematics of Operations Research , 44(1):264--276, 2019

    2019

  2. [10]

    Bubeck and C.-Y

    S. Bubeck and C.-Y. Liu. Prior-free and prior-dependent regret bounds for Thompson Sampling . Advances in neural information processing systems , 26, 2013

    2013

  3. [11]

    Bergemann and S

    D. Bergemann and S. Morris. Information Design: A Unified Perspective . Journal of Economic Literature , 57(1):44--95, 2019

    2019

  4. [12]

    Bubeck and M

    S. Bubeck and M. Sellke. First-Order Bayesian Regret Analysis of Thompson Sampling . IEEE Transactions on Information Theory , 69(3):1795--1823, 2022

    2022

  5. [13]

    Che and J

    Y.-K. Che and J. H \"o rner. Recommender systems as mechanisms for social learning. The Quarterly Journal of Economics , 133(2):871--925, 2018

    2018

  6. [14]

    Chewi and A.-A

    S. Chewi and A.-A. Pooladian. An entropic generalization of Caffarelli’s contraction theorem via covariance inequalities . Comptes Rendus. Math \'e matique , 361(G9):1471--1482, 2023

    2023

  7. [15]

    Dwivedi, Y

    R. Dwivedi, Y. Chen, M. J. Wainwright, and B. Yu. Log-concave sampling: Metropolis-Hastings algorithms are fast . Journal of Machine Learning Research , 20(183):1--42, 2019

    2019

  8. [16]

    Durmus and \'E

    A. Durmus and \'E . Moulines. High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm . Bernoulli , 25(4A), 2019

    2019

  9. [17]

    Dong and B

    S. Dong and B. Van Roy. An Information-Theoretic Analysis for Thompson Sampling with Many Actions . Advances in Neural Information Processing Systems , 31, 2018

    2018

  10. [18]

    Frazier, D

    P. Frazier, D. Kempe, J. Kleinberg, and R. Kleinberg. Incentivizing exploration. In Proceedings of the fifteenth ACM conference on Economics and computation , pages 5--22, 2014

    2014

  11. [19]

    Garber and E

    D. Garber and E. Hazan. Faster rates for the Frank-Wolfe method over strongly-convex sets . In International Conference on Machine Learning , pages 541--549. PMLR, 2015

    2015

  12. [20]

    Y. Gur, A. Kalvit, and A. Slivkins. Incentivized Exploration via Filtered Posterior Sampling . In Proceedings of the 25th ACM Conference on Economics and Computation , pages 1200--1200, 2024

    2024

  13. [21]

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

    1973

  14. [22]

    R. D. Gordon. Values of Mills' ratio of area to bounding ordinate and of the normal probability integral for large values of the argument . Ann. Math. Stat. , 12(3):364--366, 1941

    1941

  15. [23]

    Huang, T

    R. Huang, T. Lattimore, A. Gy \"o rgy, and C. 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(145):1--31, 2017

    2017

  16. [24]

    X. Hu, D. D. Ngo, A. Slivkins, and Z. S. Wu. Incentivizing Combinatorial Bandit Exploration . Advances in Neural Information Processing Systems (NeurIPS) , 2022

    2022

  17. [25]

    Immorlica, F

    N. Immorlica, F. Echenique, and V. V. Vazirani. Online and Matching-Based Market Design . Cambridge University Press, 2023

    2023

  18. [26]

    Immorlica, J

    N. Immorlica, J. Mao, A. Slivkins, and Z. S. Wu. Bayesian exploration with heterogeneous agents. In The world wide web conference , pages 751--761, 2019

    2019

  19. [27]

    Immorlica, J

    N. Immorlica, J. Mao, A. Slivkins, and Z. S. Wu. Incentivizing Exploration with Selective Data Disclosure . In Proceedings of the 21st ACM Conference on Economics and Computation , pages 647--648, 2020

    2020

  20. [28]

    Kamenica

    E. Kamenica. Bayesian Persuasion and Information Design . Annual Review of Economics , 11:249--272, 2019

    2019

  21. [29]

    Kerdreux, A

    T. Kerdreux, A. d’Aspremont, and S. Pokutta. Projection-free optimization on uniformly convex sets. In International Conference on Artificial Intelligence and Statistics , pages 19--27. PMLR, 2021

    2021

  22. [30]

    Kaufmann, N

    E. Kaufmann, N. Korda, and R. Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International conference on algorithmic learning theory , pages 199--213. Springer, 2012

    2012

  23. [31]

    Kannan, M

    S. Kannan, M. Kearns, J. Morgenstern, M. Pai, A. Roth, R. Vohra, and Z. S. Wu. Fairness incentives for myopic agents. In Proceedings of the 2017 ACM Conference on Economics and Computation , pages 369--386, 2017

    2017

  24. [32]

    Wisdom of the Crowd

    I. Kremer, Y. Mansour, and M. Perry. Implementing the “Wisdom of the Crowd” . Journal of Political Economy , 122(5):988--1012, 2014

    2014

  25. [33]

    Kerdreux, C

    T. Kerdreux, C. Roux, A. d'Aspremont, and S. Pokutta. Linear bandits on uniformly convex sets. Journal of Machine Learning Research , 22(284):1--23, 2021

    2021

  26. [34]

    Levy and A

    K. Levy and A. Krause. Projection Free Online Learning over Smooth Sets . In The 22nd International Conference on Artificial Intelligence and Statistics , pages 1458--1466. PMLR, 2019

    2019

  27. [35]

    Mhammedi

    Z. Mhammedi. Exploiting the curvature of feasible sets for faster projection-free online learning. arXiv preprint arXiv:2205.11470 , 2022

    2022 arXiv

  28. [36]

    Molinaro

    M. Molinaro. Strong Convexity of Feasible Sets in Off-line and Online Optimization . Mathematics of Operations Research , 48(2):865--884, 2023

    2023

  29. [37]

    Mansour, A

    Y. Mansour, A. Slivkins, and V. Syrgkanis. Bayesian Incentive-Compatible Bandit Exploration . Operations Research , 68(4):1132--1161, 2020. Preliminary version in ACM EC 2015

    2020

  30. [38]

    Mansour, A

    Y. Mansour, A. Slivkins, V. Syrgkanis, and S. Wu. Bayesian exploration: Incentivizing exploration in B ayesian games. Operations Research , 70(2), 2022. Preliminary version in EC 2016

    2022

  31. [39]

    R. B. Myerson. Multistage games with communication. Econometrica: Journal of the Econometric Society , pages 323--358, 1986

    1986

  32. [40]

    Nesterov and A

    Y. Nesterov and A. Nemirovskii. Interior-point polynomial algorithms in convex programming . SIAM, 1994

    1994

  33. [41]

    Russo and B

    D. Russo and B. Van Roy . Learning to Optimize via Posterior Sampling . Mathematics of Operations Research , 39(4):1221--1243, 2014

    2014

  34. [42]

    Russo and B

    D. Russo and B. Van Roy . An information-theoretic analysis of thompson sampling. JMLR , 17:68:1--68:30, 2016

    2016

  35. [43]

    M. Sellke. Incentivizing exploration with linear contexts and combinatorial actions. In International Conference on Machine Learning , pages 30570--30583. PMLR, 2023

    2023

  36. [44]

    Slivkins

    A. Slivkins. Introduction to multi-armed bandits. Foundations and Trends in Machine Learning , 12(1-2):1--286, November 2019

    2019

  37. [45]

    Sellke and A

    M. Sellke and A. Slivkins. The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity . Operations Research , 71(5):1706--1732, 2023

    2023

  38. [46]

    Simchowitz and A

    M. Simchowitz and A. Slivkins. Exploration and incentives in reinforcement learning. Operations Research , 72(3):983--998, 2024

    2024

  39. [47]

    Saumard and J

    A. Saumard and J. A. Wellner. Log-concavity and strong log-concavity: a review. Statistics surveys , 8:45, 2014

    2014

  40. [48]

    Tsuchiya and S

    T. Tsuchiya and S. Ito. Fast rates in stochastic online convex optimization by exploiting the curvature of feasible sets. In The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024

    2024

  41. [49]

    Van Handel

    R. Van Handel. Probability in high dimension. Lecture Notes (Princeton University) , 2(3):2--3, 2014

    2014

  42. [50]

    Wang and L

    S. Wang and L. Huang. Multi-armed bandits with compensation. Advances in Neural Information Processing Systems , 31, 2018

    2018

  43. [51]

    H. Wang, H. Xu, C. Li, Z. Liu, and H. Wang. Incentivizing exploration in linear contextual bandits under information gap. In Proceedings of the 17th ACM Conference on Recommender Systems , pages 415--425, 2023

    2023

  44. [52]

    Zimmert and T

    J. Zimmert and T. Lattimore. Connections between mirror descent, Thompson sampling and the information ratio . Advances in neural information processing systems , 32, 2019

    2019

Pith tools

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