Pith. sign in

REVIEW 3 major objections 5 minor 57 references

Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition

T0 review · 3 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 OIAFC identifies an $(\epsilon,\delta)$-optimal scoring rule with instance-dependent sample complexity $\tilde{O}(\varepsilon^{-2}B_S^2 M H_\Delta)$, and OIAFB matches the instance-independent rate under a fixed budget.

desk verdict Real gap between advertised and proven instance-dependent bounds, and a reversed condition in the fixed-budget pseudocode, but the approach is substantive and merits a major-revision path through peer review. read the letter →

arxiv 2505.17379 v1 pith:U7BCWR5D submitted 2025-05-23 cs.LG cs.AI

Zichen Wang , Chuanhao Li , Huazheng Wang This is my paper · ORCID
classification cs.LGcs.AI MSC 68Q3268W27
keywords bestscoringruleidentificationprincipal-agentinformationacquisitiononlinelearningfixedconfidencebudgetsamplecomplexityproperrulesUCB-LP
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 addresses best scoring rule identification (BSRI): a principal interacts repeatedly with an agent who gathers information, and must output a scoring rule that is within $\epsilon$ of optimal in the principal's profit with confidence at least $1-\delta$. It proposes OIAFC (fixed confidence) and OIAFB (fixed budget) and proves that both identify an $(\epsilon,\delta)$-optimal scoring rule with sample complexity $\tilde{O}(\varepsilon^{-2}B_S^2 M H)$, where $H$ is the instance-dependent problem complexity $H_\Delta = 4(B_S+B_u)^2(\epsilon^{-2}+\sum_{k\neq k^*}\Delta_k^{-2})$ or the instance-independent $H_\epsilon = 4(B_S+B_u)^2K/\epsilon^2$, and $M$ is the size of the belief-report support, at most $K \times C_{\mathcal{O}}$. These are, to the authors' knowledge, the first instance-dependent sample-complexity upper bounds for BSRI in this online principal-agent model, and they bring the cost of strategic information acquisition down to the familiar $\tilde{O}(\epsilon^{-2})$ form of best-arm identification in multi-armed bandits, up to problem-specific constants. A reader would care because the previous online bound of Chen et al. (2023) was instance-independent and substantially larger, so the extra strategic layer need not multiply the sample cost.

What carries the argument

The load-bearing objects are the action-informed oracle of Assumption 1, which supplies $K$ scoring rules $\tilde{S}_k$ such that announcing $\tilde{S}_k$ makes arm $k$ the agent's best response with a profit margin at least $\varepsilon$; the optimistic linear program UCB-LP$_{k,t}$, built from estimated belief distributions, estimated pairwise cost differences, and confidence radii, whose optimum is a high-probability upper bound on $h(S^*_k)$; the conservative sampling rule $S_t = \alpha_t \tilde{S}_{k^*} + (1-\alpha_t)\hat{S}_{k^*,t}$, which biases the agent toward the estimated best arm; and the binary search on the segment between $\hat{S}_{k^*,t}$ and $\tilde{S}_{k^*}$ that locates the switching boundary of the response region. The trade-off parameters $\alpha_t^k$ and the breaking threshold $\beta_t$ balance normal exploration rounds against forced-exploration binary searches, and the profit gaps $\Delta_k = h(S^*)-h(S^*_k)$ determine the instance-dependent complexity $H_\Delta$.

What would settle it

Simulate OIAFC on a synthetic instance with known belief distributions $q_k$, costs $c_k$, and oracle rules $\tilde{S}_k$; vary the oracle margin $\varepsilon$ and the suboptimality gaps $\Delta_k$, and count rounds $\tau$ until the stopping rule fires. The theorem predicts $\tau \approx \varepsilon^{-2}B_S^2 M H_\Delta$ up to logarithmic factors with probability at least $1-\delta$; a materially different scaling, or a successful identification when $\varepsilon=0$ and no oracle is supplied, would put the central claim in doubt.

Watch

Extended reading notes

Core claim

At the center is a reduction of the principal-agent information acquisition problem to a bandit-like problem in which each arm $k$ has a value $h(S^*_k)$, the principal's maximum profit when the agent's best response is $k$. The principal learns the belief distribution $q_k$ and pairwise cost differences $C(k,k')$ from interactions, builds a linear program UCB-LP$_{k,t}$ whose optimum $\hat{h}^k_t$ upper-bounds $h(S^*_k)$ with high probability, and each round announces a conservative mixture $S_t = \alpha_t \tilde{S}_{k^*} + (1-\alpha_t)\hat{S}_{k^*,t}$ of the action-informed oracle rule and the current LP solution. If the agent deviates from the intended arm, a binary search on the line segment between the two rules refines the boundary of the response region $V_k$. With $\alpha_t^k = \min(\sqrt{M/L_t^k},1)$ and a stopping threshold $\beta_t$, Theorem 1 bounds total rounds by $\tilde{O}(\varepsilon^{-2}B_S^2 M H_\Delta)$ with probability at least $1-\delta$; Corollary 1 gives $\tilde{O}(\varepsilon^{-2}B_S^2 M H_\epsilon)$ when $\alpha$ is constant; Theorem 2 and Corollary 2 show OIAFB achieves the same instance-independent rate under a fixed budget.

Load-bearing premise

The entire sample-complexity argument assumes a fixed action-informed oracle that provides, for each of the agent's actions, a scoring rule that makes that action strictly best with a profit margin of at least $\varepsilon$; if such an oracle does not exist or that margin is tiny, the forced-exploration analysis and the $\varepsilon^{-2}$ factors in the bounds no longer hold.

Editorial extensions

If this is right

  • If Theorem 1 is correct, instances with well-separated suboptimal arms are solved faster than the worst case, because the sample count depends on $\sum_{k\neq k^*}\Delta_k^{-2}$ rather than only on $K$.
  • If Corollary 1 is correct, the instance-independent sample complexity improves the previous online bound by removing a large polynomial gap and lands at the same form as classic fixed-confidence best-arm identification, up to the factor $M$ and constants.
  • If Theorem 2 and Corollary 2 are correct, a principal can commit in advance to a fixed budget $T=\tilde{O}(\varepsilon^{-2}B_S^2 M H_\epsilon)$ and still obtain the same $(\epsilon,\delta)$ identification guarantee.
  • The paper's analysis treats fixed confidence and fixed budget with the same complexity notion, suggesting that the choice between the two settings does not change the fundamental sample cost of the problem.

Reading between the lines

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

  • The paper treats the oracle margin $\varepsilon$ as a fixed constant separate from the accuracy $\epsilon$; an implicit consequence is that if the oracle is only guaranteed to work with a much smaller margin, the forced-exploration term $\varepsilon^{-2}$ in Theorem 1 would dominate, so the algorithm's practical efficiency depends on the oracle's quality, not only on the reward gaps.
  • Because the entire method is built from confidence radii for belief distributions and cost differences, a natural testable extension is to learn the action-informed rules themselves from scratch and use the LP solutions as surrogates; the paper's cited hard instance suggests this can only work under additional structure, so measuring the degradation would clarify how essential the oracle is.
  • The same UCB-LP machinery could be transferred to multi-agent versions of the problem, since the two incentive constraints (choose the intended arm and report truthfully) are already handled by separate constraints in the linear program; the paper names this direction as future work.
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

3 major / 5 minor

Summary. The paper studies best scoring rule identification (BSRI) in an online principal-agent information acquisition model. It proposes OIAFC for fixed-confidence identification and OIAFB for fixed-budget identification, both based on estimated belief distributions and pairwise cost differences, an optimism-based linear program (UCB-LP), a conservative sampling rule that mixes an action-informed oracle rule with the current LP solution, and a binary-search forced-exploration procedure. The authors claim an instance-dependent fixed-confidence bound O~(M(sum_{k≠k*} Δ_k^{-2}) + ε^{-2}), an instance-independent bound O~(M K ε^{-2}), and a matching fixed-budget result, improving on the instance-independent bound of Chen et al. (2023).

Significance. If the advertised bounds were proven, the paper would give the first instance-dependent fixed-confidence upper bound and the first fixed-budget analysis for BSRI, a natural pure-exploration variant of the online principal-agent information acquisition problem. The algorithmic machinery is nontrivial: the UCB-LP formulation, the time-varying trade-off parameter α_t^k, the stopping rule, and the binary-search analysis are all concrete and, in the instance-independent parts, the proof strategy is coherent. The paper also usefully identifies the role of the action-informed oracle margin in forced exploration. However, the central instance-dependent claim is not supported by the stated theorem, and the fixed-budget pseudocode is inconsistent with its analysis, so the main novelty is currently unproven as presented.

major comments (3)
  1. [Section 1 and Theorem 1] The introduction (first contribution bullet) advertises an instance-dependent sample complexity of O~(M(Σ_{k≠k*} Δ_k^{-2}) + ε^{-2}) for OIAFC, and Remark 4 claims that the result aligns with standard MAB instance-dependent bounds. Theorem 1 instead proves τ = O~(ε^{-2} B_S^2 M H_Δ), where H_Δ = 4(B_S+B_u)^2(ε^{-2}+Σ_{k≠k*} Δ_k^{-2}) by Definition 3. Even after suppressing logarithmic factors, the proven bound is O~(ε^{-2}B_S^2M(ε^{-2}+ΣΔ_k^{-2})), which contains an extra multiplicative ε^{-2}B_S^2M factor absent from the advertised bound. Assumption 1 only asserts that a positive oracle margin ε exists; Lemma 4 carries ε^{-1} into the forced-exploration count, and Lemma 12 does the same in the definition of N*_k. No step in Sections F or G lower-bounds ε or cancels its dependence. This is load-bearing because the paper's headline novelty is precisely the instance-dependent rate, so either the advertised bound must be proven or the claims and Remark 4 must be revised to the weaker theorem.
  2. [Appendix D.1, Algorithm 2] Algorithm 2 (OIAFB) executes the binary search when k_t = k*_t (lines 12–14), which is the reverse of OIAFC's rule in Algorithm 1, line 12, where the binary search is executed when k_t ≠ k*_t. The text in Section 5.2 states that OIAFB shares the same sampling rule and forced-exploration strategy as OIAFC, and the fixed-budget analysis (Lemma 14 and Theorem 2) counts binary searches only on rounds in which the agent deviates from the desired arm. The theorem therefore does not apply to Algorithm 2 as printed: under the printed condition, the algorithm never performs forced exploration on the deviating rounds that the analysis relies on. The condition should be reversed, or the analysis and text should be changed to match the pseudocode.
  3. [Section F.2, proof of Lemma 4] The proof of Lemma 4 decomposes τ_2 using indicators of the form 1{BS=1, Γ^{t0(t)}(k0(t),k1(t)) ≤ α^{t0(t)}_{k0(t)}} and 1{BS=1, Γ^{t0(t)}(...) > α^{t0(t)}_{k0(t)}}. The manuscript does not state a normalization or loss-of-generality assumption that would justify setting BS=1. Since every confidence radius, every UCB-LP constraint, and the definition of Γ scale with BS, this is not a harmless notational convenience. The proof should either state the normalization explicitly and show how the general case follows, or remove the condition. As written, the forced-exploration bound in Lemma 4 is not fully established for general BS.
minor comments (5)
  1. [Notation throughout] The paper uses ε both for the target accuracy ǫ in Definition 2 and for the oracle margin ε in Assumption 1, despite the notation table distinguishing the two. This ambiguity is especially confusing in Theorem 1, Lemma 4, and Definition 3, and it contributes to the mismatch identified above. Please disambiguate consistently.
  2. [Algorithm 1, line 10] The printed sampling rule contains the expression `αt_{k*}^k`, which appears to be a typo for α_t^{k*_t} as defined in the surrounding text.
  3. [Corollary 2] The budget formula in Corollary 2 contains the term max(B_S^2 ε^{-2}, 1), while the prose says the budget is O~(ε^{-2}B_S^2 M H_ǫ). These statements should be reconciled, since when B_S^2 ε^{-2} < 1 the printed formula does not contain the ε^{-2}B_S^2 factor.
  4. [Appendix D.2, Algorithm 3 discussion] In the paragraph following Algorithm 3, the text refers to k*(S2), although the algorithm signature names the two inputs k*(S0) and k*(S1). This appears to be a typo.
  5. [Throughout] There are several typographical errors in the text, including 'involes', 'incurrs', and 'principal' for 'principle' in the introduction; these do not affect the technical content but should be corrected in revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; the advertised instance-dependent bound is mismatched with Theorem 1, but that is a correctness gap, not a circular reduction.

full rationale

Walking the derivation chain, the core sample-complexity analysis is self-contained in the relevant sense: Lemma 2 follows from the concentration inequality of Mardia et al. (2018) applied to the empirical belief estimator; Lemmas 3, 4, 5, 7, 8, 9, 10, and 12 are proved in the paper from the UCB-LP formulation and the stated stopping and sampling rules; and the final bounds in Theorem 1 and Corollaries 1-2 are obtained by algebraically combining those lemmas. The only imported technical results, Lemma 11 (Proposition F.9 of Chen et al. 2023) and Lemma 13 (Lemma F.4 of Chen et al. 2023), come from a different prior paper, so no load-bearing self-citation chain is present. Assumption 1 is an explicit oracle assumption inherited from Chen et al. (2023), and the dependence of the bound on the oracle margin epsilon is an assumption-consequence, not a definitional equivalence; no fitted parameter is relabeled as a prediction, and no quantity that appears in the theorem is defined in terms of the output it is supposed to predict. There is a genuine discrepancy between the introduction's advertised bound, O-tilde(M(sum_{k != k*} Delta_k^{-2}) + epsilon^{-2}), and the proven Theorem 1 bound, O-tilde(epsilon^{-2} B_S^2 M H_Delta), which also contains epsilon^{-2} inside H_Delta; likewise Algorithm 2 line 13 appears to trigger binary search on kt = k*_t, opposite to the analysis. Those are correctness and presentation issues, not circularity, because the proven bound is still derived from observable estimators and concentration arguments rather than from its own conclusion. Accordingly, no circular step is identified.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted to data; the algorithm's parameters alpha_t^k and beta_t are adaptive design choices. The main hidden quantity is the oracle margin eps, an assumption rather than a fitted constant. No new physical or conceptual entities are postulated; the only new objects are the algorithm parameters themselves.

assumptions (6)
  • domain assumption Action-informed oracle (Assumption 1): there exist K scoring rules tilde S_k such that the agent's best response to tilde S_k is arm k with profit gap at least eps vs any other arm.
    Used for initialization (Alg. 1 lines 2-4), conservative sampling rule S_t = alpha tilde S_k* + (1-alpha) hat S_{k*,t}, and every binary search; the final bounds scale as eps^{-2}. Without this oracle, Chen et al. present a hard instance where no algorithm can identify the best arm.
  • standard math Revelation principle (Lemma 1): optimal scoring rules can be taken proper, so the agent reports truthfully and the problem reduces to LP (6).
    Inherited from Myerson (1979) and Chen et al. (2023); essential for the linear-programming reformulation and for using reports as observations of sigma.
  • domain assumption The agent is fully rational and knows the costs c_k and observation distributions q_k; the principal observes the chosen action k_t.
    The interaction protocol in Section 3.1 and Table 1; the agent's best responses define V_k and the principal's observation of k_t is needed to estimate q_k and C(k,k').
  • domain assumption Scoring rules and utility are bounded: ||S||_inf <= B_S and ||u||_inf <= B_u.
    Used in Lemma 2 to convert L1 concentration into bounds on |hat v_S(k) - v_S(k)| and |hat u_k - u_k|; also appears in the definitions of H_Delta and H_eps.
  • domain assumption The belief support Sigma is finite with M <= K * C_O.
    Required for the finite-support empirical concentration bound (Lemma 6) and for M to appear as a parameter in the complexity bounds.
  • domain assumption The feasible scoring-rule set S is closed under convex combinations (implicitly used in binary search and conservative rule S_t).
    Binary search (Algorithm 3) and the sampling rules use convex combinations alpha tilde S_k + (1-alpha) hat S_{k,t}; properness is preserved under convexity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition." pith.science (2026). https://pith.science/paper/U7BCWR5D

@misc{pith2026250517379,
  author       = {Pith},
  title        = {Pith review of: Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U7BCWR5D}},
  note         = {Machine review of arXiv:2505.17379}
}
abstract

We investigate the problem of identifying the optimal scoring rule within the principal-agent framework for online information acquisition problem. We focus on the principal's perspective, seeking to determine the desired scoring rule through interactions with the agent. To address this challenge, we propose two algorithms: OIAFC and OIAFB, tailored for fixed confidence and fixed budget settings, respectively. Our theoretical analysis demonstrates that OIAFC can extract the desired $(\epsilon, \delta)$-scoring rule with a efficient instance-dependent sample complexity or an instance-independent sample complexity. Our analysis also shows that OIAFB matches the instance-independent performance bound of OIAFC, while both algorithms share the same complexity across fixed confidence and fixed budget settings.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

57 extracted references · 42 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Dynamic pricing and learning with bayesian persuasion

    Agrawal, S., Feng, Y., and Tang, W. Dynamic pricing and learning with bayesian persuasion. Advances in Neural Information Processing Systems, 36, 2024

    work page 2024

  3. [3]

    Contracts with private cost per unit-of-effort

    Alon, T., D \"u tting, P., and Talgam-Cohen, I. Contracts with private cost per unit-of-effort. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp.\ 52--69, 2021

    work page 2021

  4. [4]

    Learning prices for repeated auctions with strategic buyers

    Amin, K., Rostamizadeh, A., and Syed, U. Learning prices for repeated auctions with strategic buyers. In Neural Information Processing Systems, 2013. URL https://api.semanticscholar.org/CorpusID:6702525

    work page 2013

  5. [5]

    On the complexity of differentially private best-arm identification with fixed confidence

    Azize, A., Jourdan, M., Al Marjani, A., and Basu, D. On the complexity of differentially private best-arm identification with fixed confidence. Advances in Neural Information Processing Systems, 36, 2024

    work page 2024

  6. [6]

    E., Castiglioni, M., Marchesi, A., and Gatti, N

    Bacchiocchi, F., Stradi, F. E., Castiglioni, M., Marchesi, A., and Gatti, N. Markov persuasion processes: Learning to persuade from scratch. arXiv preprint arXiv:2402.03077, 2024

    arXiv 2024

  7. [7]

    Balcan, M.-F., Blum, A., Haghtalab, N., and Procaccia, A. D. Commitment without regrets: Online learning in stackelberg security games. Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015. URL https://api.semanticscholar.org/CorpusID:14830193

    work page 2015

  8. [8]

    Principal-agent reward shaping in mdps

    Ben-Porat, O., Mansour, Y., Moshkovitz, M., and Taitler, B. Principal-agent reward shaping in mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp.\ 9502--9510, 2024

    2024

Show all 57 references
  1. [9]

    Sequential information design: Learning to persuade in the dark

    Bernasconi, M., Castiglioni, M., Marchesi, A., Gatti, N., and Trov \`o , F. Sequential information design: Learning to persuade in the dark. ArXiv, abs/2209.03927, 2022. URL https://api.semanticscholar.org/CorpusID:252118633

    2022 arXiv

  2. [10]

    Optimal rates and efficient algorithms for online bayesian persuasion

    Bernasconi, M., Castiglioni, M., Celli, A., Marchesi, A., Trov \`o , F., and Gatti, N. Optimal rates and efficient algorithms for online bayesian persuasion. ArXiv, abs/2303.01296, 2023. URL https://api.semanticscholar.org/CorpusID:262231443

    2023 arXiv

  3. [11]

    Pure exploration in multi-armed bandits problems

    Bubeck, S., Munos, R., and Stoltz, G. Pure exploration in multi-armed bandits problems. In International Conference on Algorithmic Learning Theory, 2009

    2009

  4. [12]

    Online information acquisition: Hiring multiple agents

    Cacciamani, F., Castiglioni, M., and Gatti, N. Online information acquisition: Hiring multiple agents. arXiv preprint arXiv:2307.06210, 2023

    2023 arXiv

  5. [13]

    Online bayesian persuasion

    Castiglioni, M., Celli, A., Marchesi, A., and Gatti, N. Online bayesian persuasion. In Neural Information Processing Systems, 2020. URL https://api.semanticscholar.org/CorpusID:227275502

    2020

  6. [14]

    Multi-receiver online bayesian persuasion

    Castiglioni, M., Marchesi, A., Celli, A., and Gatti, N. Multi-receiver online bayesian persuasion. ArXiv, abs/2106.06480, 2021. URL https://api.semanticscholar.org/CorpusID:235417398

    2021 arXiv

  7. [15]

    Bayesian persuasion meets mechanism design: Going beyond intractability with type reporting

    Castiglioni, M., Marchesi, A., and Gatti, N. Bayesian persuasion meets mechanism design: Going beyond intractability with type reporting. ArXiv, abs/2202.00605, 2022. URL https://api.semanticscholar.org/CorpusID:246442180

    2022 arXiv

  8. [16]

    Principal-driven reward design and agent policy alignment via bilevel-rl

    Chakraborty, S., Bedi, A., Koppel, A., Huang, F., and Wang, M. Principal-driven reward design and agent policy alignment via bilevel-rl

  9. [17]

    Towards instance optimal bounds for best arm identification

    Chen, L., Li, J., and Qiao, M. Towards instance optimal bounds for best arm identification. In Annual Conference Computational Learning Theory, 2016. URL https://api.semanticscholar.org/CorpusID:11275420

    2016

  10. [18]

    Learning to incentivize information acquisition: Proper scoring rules meet principal-agent model

    Chen, S., Wu, J., Wu, Y., and Yang, Z. Learning to incentivize information acquisition: Proper scoring rules meet principal-agent model. In International Conference on Machine Learning, pp.\ 5194--5218. PMLR, 2023

    2023

  11. [19]

    and Yu, F.-Y

    Chen, Y. and Yu, F.-Y. Optimal scoring rule design. arXiv preprint arXiv:2107.07420, 2021

    2021 arXiv

  12. [20]

    Learning approximately optimal contracts

    Cohen, A., Deligkas, A., and Koren, M. Learning approximately optimal contracts. In International Symposium on Algorithmic Game Theory, pp.\ 331--346. Springer, 2022

    2022

  13. [21]

    On stackelberg mixed strategies

    Conitzer, V. On stackelberg mixed strategies. Synthese, 193: 0 689 -- 703, 2015. URL https://api.semanticscholar.org/CorpusID:726054

    2015

  14. [22]

    Pac bounds for multi-armed bandit and markov decision processes

    Even-Dar, E., Mannor, S., and Mansour, Y. Pac bounds for multi-armed bandit and markov decision processes. In Annual Conference Computational Learning Theory, 2002. URL https://api.semanticscholar.org/CorpusID:12757817

    2002

  15. [23]

    Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems

    Even-Dar, E., Mannor, S., and Mansour, Y. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. J. Mach. Learn. Res., 7: 0 1079--1105, 2006

    2006

  16. [24]

    Learning to bid without knowing your value

    Feng, Z., Podimata, C., and Syrgkanis, V. Learning to bid without knowing your value. Proceedings of the 2018 ACM Conference on Economics and Computation, 2017. URL https://api.semanticscholar.org/CorpusID:20746015

    2018

  17. [25]

    Multi-bandit best arm identification

    Gabillon, V., Ghavamzadeh, M., Lazaric, A., and Bubeck, S. Multi-bandit best arm identification. In NIPS, 2011. URL https://api.semanticscholar.org/CorpusID:13982470

    2011

  18. [26]

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

    Gabillon, V., Ghavamzadeh, M., and Lazaric, A. Best arm identification: A unified approach to fixed budget and fixed confidence. In NIPS, 2012

    2012

  19. [27]

    Gan, J., Majumdar, R., Radanovic, G., and Singla, A. K. Bayesian persuasion in sequential decision-making. ArXiv, abs/2106.05137, 2021. URL https://api.semanticscholar.org/CorpusID:235376944

    2021 arXiv

  20. [28]

    and Kaufmann, E

    Garivier, A. and Kaufmann, E. Optimal best arm identification with fixed confidence. In Annual Conference Computational Learning Theory, 2016. URL https://api.semanticscholar.org/CorpusID:1278907

    2016

  21. [29]

    Golrezaei, N., Javanmard, A., and Mirrokni, V. S. Dynamic incentive-aware learning: Robust pricing in contextual auctions. Microeconomics: Production, 2018. URL https://api.semanticscholar.org/CorpusID:169598123

    2018

  22. [30]

    I., and Vitercik, E

    Guo, W., Jordan, M. I., and Vitercik, E. No-regret learning in partially-informed auctions. In International Conference on Machine Learning, 2022. URL https://api.semanticscholar.org/CorpusID:247025560

    2022

  23. [31]

    Learning in stackelberg games with non-myopic agents

    Haghtalab, N., Lykouris, T., Nietert, S., and Wei, A. Learning in stackelberg games with non-myopic agents. Proceedings of the 23rd ACM Conference on Economics and Computation, 2022. URL https://api.semanticscholar.org/CorpusID:250497033

    2022

  24. [32]

    Learning in online principal-agent interactions: The power of menus

    Han, M., Albert, M., and Xu, H. Learning in online principal-agent interactions: The power of menus. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp.\ 17426--17434, 2024

    2024

  25. [33]

    D., Shan, L., Li, Y., and Wu, Y

    Hartline, J. D., Shan, L., Li, Y., and Wu, Y. Optimal scoring rules for multi-dimensional effort. In The Thirty Sixth Annual Conference on Learning Theory, pp.\ 2624--2650. PMLR, 2023

    2023

  26. [34]

    Ho, C.-J., Slivkins, A., and Vaughan, J. W. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. In Proceedings of the fifteenth ACM conference on Economics and computation, pp.\ 359--376, 2014

    2014

  27. [35]

    Ivanov, D., D \"u tting, P., Talgam-Cohen, I., Wang, T., and Parkes, D. C. Principal-agent reinforcement learning. arXiv preprint arXiv:2407.18074, 2024

    2024 arXiv

  28. [36]

    I., and Steinhardt, J

    Jagadeesan, M., Wei, A., Wang, Y., Jordan, M. I., and Steinhardt, J. Learning equilibria in matching markets from bandit feedback. ArXiv, abs/2108.08843, 2021. URL https://api.semanticscholar.org/CorpusID:237213319

    2021 arXiv

  29. [37]

    G., Malloy, M., Nowak, R

    Jamieson, K. G., Malloy, M., Nowak, R. D., and Bubeck, S. lil' ucb : An optimal exploration algorithm for multi-armed bandits. ArXiv, abs/1312.7308, 2013. URL https://api.semanticscholar.org/CorpusID:2606438

    2013 arXiv

  30. [38]

    Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is q-learning provably efficient? In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 201...

    2018

  31. [39]

    Pac subset selection in stochastic multi-armed bandits

    Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, P. Pac subset selection in stochastic multi-armed bandits. In International Conference on Machine Learning, 2012. URL https://api.semanticscholar.org/CorpusID:1635758

    2012

  32. [40]

    and Maskin, E

    Laffont, J.-J. and Maskin, E. The theory of incentives: An overview. Universit \'e des sciences sociales, Facult \'e des sciences \'e conomiques, 1981

    1981

  33. [41]

    D., Shan, L., and Wu, Y

    Li, Y., Hartline, J. D., Shan, L., and Wu, Y. Optimization of scoring rules. In Proceedings of the 23rd ACM Conference on Economics and Computation, pp.\ 988--989, 2022

    2022

  34. [42]

    and Tsitsiklis, J

    Mannor, S. and Tsitsiklis, J. N. The sample complexity of exploration in the multi-armed bandit problem. In Journal of machine learning research, 2004

    2004

  35. [43]

    D., and Weissman, T

    Mardia, J., Jiao, J., T \'a nczos, E., Nowak, R. D., and Weissman, T. Concentration inequalities for the empirical distribution. ArXiv, abs/1809.06522, 2018. URL https://api.semanticscholar.org/CorpusID:52298313

    2018 arXiv

  36. [44]

    Myerson, R. B. Incentive compatibility and the bargaining problem. Econometrica, 47: 0 61--73, 1979. URL https://api.semanticscholar.org/CorpusID:152651312

    1979

  37. [45]

    Neyman, E., Noarov, G., and Weinberg, S. M. Binary scoring rules that incentivize precision. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp.\ 718--733, 2021

    2021

  38. [46]

    and Conitzer, V

    Oesterheld, C. and Conitzer, V. Minimum-regret contracts for principal-expert problems. In International Conference on Web and Internet Economics, pp.\ 430--443. Springer, 2020

    2020

  39. [47]

    and Waggoner, B

    Papireddygari, M. and Waggoner, B. Contracts with information acquisition, via scoring rules. In Proceedings of the 23rd ACM Conference on Economics and Computation, pp.\ 703--704, 2022

    2022

  40. [48]

    Savage, L. J. Elicitation of personal probabilities and expectations. Journal of the American Statistical Association, 66: 0 783--801, 1971. URL https://api.semanticscholar.org/CorpusID:120427654

    1971

  41. [49]

    Scheid, A., Tiapkin, D., Boursier, E., Capitaine, A., Mhamdi, E. M. E., Moulines, \'E ., Jordan, M. I., and Durmus, A. Incentivized learning in principal-agent bandit games. arXiv preprint arXiv:2403.03811, 2024

    2024 arXiv

  42. [50]

    G., Bogunovic, I., Kamgarpour, M., and Krause, A

    Sessa, P. G., Bogunovic, I., Kamgarpour, M., and Krause, A. Learning to play sequential games versus unknown opponents. ArXiv, abs/2007.05271, 2020. URL https://api.semanticscholar.org/CorpusID:220487073

    2007 arXiv

  43. [51]

    Pure exploration in asynchronous federated bandits

    Wang, Z., Li, C., Song, C., Wang, L., Gu, Q., and Wang, H. Pure exploration in asynchronous federated bandits. arXiv preprint arXiv:2310.11015, 2023

    2023 arXiv

  44. [52]

    I., and Xu, H

    Wu, J., Zhang, Z., Feng, Z., Wang, Z., Yang, Z., Jordan, M. I., and Xu, H. Sequential information design: Markov persuasion process and its efficient reinforcement learning. Proceedings of the 23rd ACM Conference on Economics and Computation, 2022. URL https://api.semanticscho...

    2022

  45. [53]

    Contractual reinforcement learning: Pulling arms with invisible hands

    Wu, J., Chen, S., Wang, M., Wang, H., and Xu, H. Contractual reinforcement learning: Pulling arms with invisible hands. arXiv preprint arXiv:2407.01458, 2024

    2024 arXiv

  46. [54]

    Zhu, B., Bates, S., Yang, Z., Wang, Y., Jiao, J., and Jordan, M. I. The sample complexity of online contract design. Proceedings of the 24th ACM Conference on Economics and Computation, 2022. URL https://api.semanticscholar.org/CorpusID:253447009

    2022

  47. [55]

    Learning to persuade on the fly: Robustness against ignorance

    Zu, Y., Iyer, K., and Xu, H. Learning to persuade on the fly: Robustness against ignorance. Proceedings of the 22nd ACM Conference on Economics and Computation, 2021. URL https://api.semanticscholar.org/CorpusID:231986327

    2021

  48. [56]

    New perspectives in online contract design: Heterogeneous, homogeneous, non-myopic agents and team production

    Zuo, S. New perspectives in online contract design: Heterogeneous, homogeneous, non-myopic agents and team production. arXiv preprint arXiv:2403.07143, 2024 a

    2024 arXiv

  49. [57]

    Principal-agent multitasking: the uniformity of optimal contracts and its efficient learning via instrumental regression

    Zuo, S. Principal-agent multitasking: the uniformity of optimal contracts and its efficient learning via instrumental regression. arXiv preprint arXiv:2405.20642, 2024 b

    2024 arXiv

Pith tools

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