REVIEW 2 major objections 4 minor 37 references
Learning to Lead: Incentivizing Strategic Agents in the Dark
T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A principal who sees only her own rewards and the agent's reported types can still learn a near-optimal coordination mechanism, achieving $\tilde{O}(\sqrt{T})$ strategic regret against a non-myopic agent who hides his type, action, and…
desk verdict Genuine advance in online principal-agent learning with a real but repairable sign error in the key delay-versus-IC-margin step; deserves peer review. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery has three parts. (1) A delaying mechanism: the principal withholds recent observations from policy updates for $\ell$ rounds, so the agent's current behavior can affect his future reward only through a $\gamma^\ell$-discounted term; with $\ell = \lceil\log n\rceil^2$ the agent's report is forced within $O(\gamma^\ell/(1-\gamma))$ of the myopic best report. (2) Reward angles: each normalized agent reward vector $v_\theta$ (unit, orthogonal to $\mathbf{1}_d$) is carried by an isometry $\varphi_0$ to $S^{d-2}$ and parameterized by spherical coordinates $\alpha^\theta = (\alpha^\theta_1,\ldots,\alpha^\theta_{d-2})$, called the reward angles; a sector test $\mathrm{SecTest}(\alpha,\delta)$ deploys mechanisms testing angles $\alpha-\delta$, $\alpha$, $\alpha+\delta$ and reads which row the agent reports to decide whether some true angle lies in $(\alpha-\delta/2,\alpha+\delta/2)$, and a reverse-order gluing procedure with conditional sector tests assembles coordinate estimates into full vectors despite unknown type labels. (3) Pessimistic-optimistic LinUCB: the principal solves $\max_{(\Pi,\beta)\in I_n \times C_k}\langle\Pi,\beta\rangle$, optimizing an optimistic ridge-regression objective over a pessimistic constraint set $I_n = \bigcap_{V\in\mathcal{V}_n} \mathrm{IC}(V)$ that keeps the mechanism incentive-compatible against every reward matrix consistent with the angle estimates.
What would settle it
Run the angle-estimation stage on the minimal ambiguous instance: $d=3$, $\Theta=\{1,2\}$, with normalized reward vectors $v_1 = -v_2$, keeping every other assumption intact. The paper's analysis says the sector test then cannot separate the types — reported-type counts become type-symmetric, so the estimate $\hat\alpha$ cannot resolve which angle belongs to which label and the loss $D(\alpha,\hat\alpha)$ should plateau at a constant floor regardless of the sample budget $n$; a simulation showing the error instead decaying polynomially would refute the necessity of the non-antipodal premise. On the positive side, the same simulator should reproduce the claimed $D(\alpha,\hat\alpha) \le C_2|\Theta|^{-1}n^{-50}$ rate on generic instances, which is a direct check of the estimation guarantee in Theorem 3.2.
Extended reading notes
Core claim
The central claim is that unknown reward functions can be learned well enough to support near-optimal mechanism design: under Assumptions 2.1, 2.2, 2.3 and 3.1, Algorithm 1 — and its anytime variant with a doubling trick — has expected strategic regret $E[\mathrm{Regret}(T)] \le C\sqrt{T}(\log T)^3$, together with an asymptotic version $\mathrm{Regret}(T)/(\sqrt{T}(\log T)^{g_0}) \to 0$ for $g_0 > 3$ and a high-probability bound with an additive $\varepsilon^{-1/10}(\log\varepsilon^{-1})^2$ term. The benchmark $u^*$ is the value of the linear program (LP*) that characterizes the optimal truthful mechanism when the agent is myopic, and the revelation principle makes this the right yardstick even for a non-myopic agent. The argument rests on three load-bearing ideas: a delaying scheme that buys approximately myopic behavior from the agent with a $\gamma^\ell$-discounted error, an angle-based pipeline that recovers the normalized reward vectors from reported-type data, and a pessimistic-optimistic LinUCB that explores the principal's linear reward while restricting to mechanisms that are incentive-compatible against every plausible reward estimate.
Load-bearing premise
The load-bearing premise is that the agent's normalized reward vectors are all distinct and no two point in exactly opposite directions, so that types remain identifiable from reported-type data and the random rotation used in Lemma 3.2 can produce the generic angle configuration with probability one.
Editorial extensions
If this is right
- The principal can achieve $\tilde{O}(\sqrt{T})$ strategic regret without ever observing the agent's type, action, or reward: reported types plus her own realized rewards suffice.
- Only $O((\log T)^5)$ rounds are needed to estimate the full collection of type-dependent reward functions at $T^{-50}$-scale accuracy, so estimation consumes a vanishing share of the horizon.
- The same regret rate holds when the horizon $T$ is unknown, via an episodic doubling trick that restarts the estimation and planning stages with geometrically growing budgets.
- The estimated feasible region is pessimistic by construction — a subset of the true incentive-compatible region up to type permutation — which turns constraint-estimation error into bounded loss rather than incentive violation.
- The high-probability version of the bound has an additive $\varepsilon^{-1/10}(\log\varepsilon^{-1})^2$ term, so shrinking the failure probability degrades the guarantee only mildly.
Reading between the lines
- The sector-test-and-matching pipeline is a transferable template: any problem in which a learner must recover a set of unlabeled type-dependent parameters from strategic reports could reuse the same binary-search primitive, for instance to relax the finite-type assumption to a continuum with a separation scale in place of the generic-position conditions.
- The argument never uses the agent's discount factor $\gamma$ except through the delay length, so the algorithm plausibly tolerates unknown or time-varying discount factors bounded away from 1; the delay schedule only needs to be stretched logarithmically in the desired myopia error.
- A natural stress test of the identifiability premise is to run the angle estimator on instances whose normalized reward vectors are equal or antipodal; the analysis predicts an error floor that no amount of samples cures, which would be a useful diagnostic for whether such separation assumptions are truly required in practice.
- The exponential dependence of the constants on dimension is inherited from existing Stackelberg-style lower bounds; whether the spherical-coordinate parametrization admits dimension-friendlier sample complexity under sparsity of the reward angles is an open question the paper does not address.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies an online generalized principal-agent model in which a principal repeatedly interacts with a non-myopic, strategic agent with private types, private rewards, and private actions. The principal observes only reported types and her own realized rewards, and she does not know the reward functions, the type distribution, the discount factor, or (in the anytime version) the horizon. The proposed algorithm combines a delaying scheme intended to make the agent approximately myopic, a reward-angle estimation routine based on sector tests and permutation matching, and a pessimistic-optimistic LinUCB procedure. The main claimed result is E[Regret(T)] = O(√T (log T)^3), together with asymptotic and high-probability variants, against the myopic oracle benchmark u* defined by the linear program (LP*). The proof is structured through a sequence of lemmas with appendices, and a doubling trick is used to handle unknown T.
Significance. If the result holds, this is a substantial advance: it would be the first sample-efficient algorithm for the generalized principal-agent model with private types, private rewards, unobservable actions, and a strategically forward-looking agent. The algorithmic pipeline is novel in combining delay-based myopic approximation, spherical-coordinate estimation of normalized reward vectors via sector tests, and a pessimistic treatment of incentive-compatibility constraints in a linear bandit. The paper also provides explicit regularity assumptions, a revelation-principle reduction, and detailed appendix proofs for most components. The main obstacle is a concrete proof gap in the incentive-compatibility step; because the gap is local and appears repairable without changing the algorithm, the manuscript merits major revision rather than rejection.
major comments (2)
- [Appendix C.6, proof of Theorem B.1] The proof states: "Let k0 ∈ N+ such that for all k ≥ k0, 2B γ^{⌈log n_k⌉^2}/(1−γ) > 2^{−40k}." This is the reverse of what the argument needs. To conclude that the agent "will always report s" under a mechanism in I_{n_k}, the delay-induced myopia error must be smaller than the IC margin n_k^{-40} = 2^{-40k} appearing in the constraints (20). Lemma 3.1 only bounds the strategic agent's report by C0 γ^{ell}/(1−γ) in normalized units (Eq. (11)), so if the displayed inequality holds, the margin is insufficient to rule out misreporting. The reduction of the planning stage to a stochastic linear bandit with truthful reports is therefore not established as written. In addition, the bound should use the constant C0 from Lemma 3.1 rather than 2B. The gap is repairable: choosing ell (or k0) so that C0 γ^{ell}/(1−γ) < 2^{-40k} is possible because γ^{O((log n_k)^2)} decays faster than 2^{-40k} for large k, but the corrected inequality must be stated and used.
- [Section 3.2 and Lemma 3.2] The claim that the four conditions of Assumption 3.1 hold "with probability one through a random rotation" is conditional on the non-antipodal condition v_θ ≠ -v_{θ'} stated immediately before Lemma 3.2. That non-antipodal condition is not listed among Assumptions 2.1–2.3, and the formal theorems are stated under Assumptions 2.1, 2.2, 2.3 and 3.1. Since the non-antipodal condition is a substantive restriction on the instance that cannot be removed by any random isometry, it should be stated explicitly as a formal assumption in Theorem 3.2, Theorem 3.3, and Theorem B.1, or the text should say that Assumption 3.1 is not guaranteed by the random rotation unless this condition holds.
minor comments (4)
- [Appendix C.6] The same displayed inequality uses 2B instead of the normalized constant C0 from Lemma 3.1; even with the direction corrected, the normalization in Eq. (11) requires C0 = 2B / min_θ ||v_θ − 1_d ⟨1_d, v_θ⟩/d||_2.
- [Section 4] The text says the |Θ|=2 case is handled by analogy and refers to Appendix D.4.3, but it also states "We skip the details to avoid redundancy." Since Theorem 3.3 covers all |Θ| ≥ 2, the paper should either include the complete proof of the |Θ|=2 case in the appendix or explicitly mark it as a separate assumption; a pointer without a full proof makes the theorem's range hard to verify.
- [Section 2.1] The cross-reference "See Figure 11 for an illustration" should be "Figure 1", and the sentence "the the feasible region" in Section 3.2 contains a doubled definite article.
- [Section 3.3] In the sentence introducing V_n, the matrix V_n^* is defined by "the s-th row of this matrix is set to v_{b_n^*(s)}"; it would clarify that b_n^* is the random permutation from Eq. (18) and that the algorithm never needs to know it.
Circularity Check
No significant circularity; the regret bound follows from stated model assumptions and an independently defined myopic-oracle benchmark.
full rationale
The derivation chain is self-contained. The benchmark u* is defined by (LP*)/(OPT*) from the true reward vectors and type distribution, with no dependence on Algorithm 1 or the estimated parameters. The regret analysis in Theorem B.1 compares the algorithm's expected reward to u* through the estimated feasible set I_n, whose proximity to the true feasible set is established in Lemma B.1 via perturbation arguments and LP duality, not by assuming the desired regret bound. The data-dependent permutation b*_n is used only as an analytical labeling device; the optimization objective in (22) is permutation-invariant, so this does not turn the conclusion into an input. The reward-angle estimation guarantees (Theorem 3.2, Lemma 4.2) are derived from binary-search sector tests and concentration arguments with polylogarithmic sample complexity, independent of the regret bound. The self-citations present (e.g., Zhu et al. 2022 for exponential dimension dependence, Chen et al. 2023b for binary-search cost estimation) are contextual or remarks and are not load-bearing. One genuine issue exists in Appendix C.6: the displayed condition '2B gamma^{ceil(log n_k)^2}/(1-gamma) > 2^{-40k}' has the wrong inequality direction for the intended 'delay error smaller than IC margin' argument, and the constant should be C0 rather than 2B. That is a correctness gap in the proof, not a circularity, because it does not make the regret bound an input of the derivation. Overall circularity is low.
Assumptions & free parameters
free parameters (4)
- Delay length ell = ceil(log n)^2
- Sector-test duration T_sec = ceil(log n)^4
- IC margin n^{-40} and confidence radius n^{-50}
- Binary-search depth K = ceil(4^{d+1} log2 n) + 1
assumptions (7)
- domain assumption Assumption 2.1: there exists an interior feasible coordination mechanism with an epsilon-ball margin.
- domain assumption Assumption 2.2: normalized reward vectors are distinct and not parallel to the all-ones vector.
- domain assumption Assumption 2.3: positive type probabilities, bounded rewards, and strict best responses.
- ad hoc to paper Non-antipodal condition: v_theta != -v_theta' for all distinct theta, theta'.
- domain assumption Assumption 3.1: four generic-position conditions on reward angles.
- standard math Standard linear bandit confidence ellipsoids (Abbasi-Yadkori et al., 2011).
- standard math Strong duality for finite linear programs.
Cite this review
Pith. "Pith review of Learning to Lead: Incentivizing Strategic Agents in the Dark." pith.science (2026). https://pith.science/paper/32DNTH3U
@misc{pith2026250608438,
author = {Pith},
title = {Pith review of: Learning to Lead: Incentivizing Strategic Agents in the Dark},
year = {2026},
howpublished = {\url{https://pith.science/paper/32DNTH3U}},
note = {Machine review of arXiv:2506.08438}
}
abstract
We study an online learning version of the generalized principal-agent model, where a principal interacts repeatedly with a strategic agent possessing private types, private rewards, and taking unobservable actions. The agent is non-myopic, optimizing a discounted sum of future rewards and may strategically misreport types to manipulate the principal's learning. The principal, observing only her own realized rewards and the agent's reported types, aims to learn an optimal coordination mechanism that minimizes strategic regret. We develop the first provably sample-efficient algorithm for this challenging setting. Our approach features a novel pipeline that combines (i) a delaying mechanism to incentivize approximately myopic agent behavior, (ii) an innovative reward angle estimation framework that uses sector tests and a matching procedure to recover type-dependent reward functions, and (iii) a pessimistic-optimistic LinUCB algorithm that enables the principal to explore efficiently while respecting the agent's incentive constraints. We establish a near optimal $\tilde{O}(\sqrt{T}) $ regret bound for learning the principal's optimal policy, where $\tilde{O}(\cdot) $ omits logarithmic factors. Our results open up new avenues for designing robust online learning algorithms for a wide range of game-theoretic settings involving private types and strategic agents.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[1]
(Expected reward) There exists a positive constantC∗ that depends only on(P, φ0), such that for all T∈N + andT≥2, we have E[Regret(T)]≤C ∗ √ T·(logT) 3
-
[2]
(Asymptotic regret) For anyg0 >3, asT→ ∞ Regret(T)√ T·(logT) g0 a.s. →0
-
[3]
Proof of Theorem B.1.We defer the proof of the theorem to Appendix C.6
(High-probability bound) There exists a positive constantC′ ∗ that depends only on(P, φ0), such that for allT∈N +, with probability at least1−ε, Regret(T)≤C ′ ∗ · √ T·(logT) 3 +ε −1/10 ·(logε −1)2 . Proof of Theorem B.1.We defer the proof of the theorem to Appendix C.6. 37 Appendix C Proofs for regret upper bound We present in this section proofs related ...
work page 2011
-
[4]
Ifθ t =b n(jℓ)for someℓ∈[|Θ| −2], then the agent will always report typeℓ+ 2in roundt
-
[5]
By the nature of the pessimistic-optimistic planning stage, in order to upper bound the regret, it suffices to consider the regret that arises from roundsj(⌈logn k⌉2 + 1) + 1, withj= 0,1,· · ·, nk −1. Forn∈ [nk ·(⌈logn k⌉2 + 1)], we denote byR2,k,n the total regret that arises from the firstnrounds of the pessimistic- optimistic planning stage. Letjn = ma...
-
[6]
We make the convention thatχd−2 =eχd−2 =∞
Fori∈[d−3], we define χi := min θ̸=θ′,θ,θ′∈Θ |αθ i −π/2| − |αθ′ i −π/2| , eχi := min θ∈Θ min n |αθ i |,|α θ i −π|,|α θ i −π/2|,0.1 o . We make the convention thatχd−2 =eχd−2 =∞
-
[7]
46 We note that Assumption 3.1 implies thatχi,eχi, χi are all strictly positive
Fori∈[d−2], we let χi := min θ̸=θ′,θ,θ′∈Θ min n arc(αθ i , αθ′ i ),arc(α θ i , αθ′ i +π) o , where we recall thatarcis defined in Section 1.2. 46 We note that Assumption 3.1 implies thatχi,eχi, χi are all strictly positive. Now we are ready to prove Lemma 4.1. Proof of Lemma 4.1.We choosen 0 large enough such that it satisfies the requirement of Lemma D.1...
-
[8]
Namely,(A2) holds throughout the firstjrounds
For currentMand allh∈ M, it holds that∥bαh i:(d−2) −α bn(h) i:(d−2)∥1 ≤4(d−1−i)·n −4i+3 . Namely,(A2) holds throughout the firstjrounds
Show all 37 references
-
[9]
Namely,(A3)holds throughout the firstjrounds
For currentM, allθ∈Θ\{b n(j) :j∈ M}andθ ′ ∈ {bn(j) :j∈ M}, it holds that |αθ i −π/2|>min{|α−δ/2−π/2|,|α+δ/2−π/2|}>|α θ′ i −π/2|. Namely,(A3)holds throughout the firstjrounds. Here, recallαis the center of the testing interval andδis the interval length. In this lemma, we defin...
-
[10]
Then (a) Ifα > π/2andα θt i ∈[α−δ, π], then the agent will never report typer= 1in roundt
Suppose in roundtwe haveθ t ̸=θ p. Then (a) Ifα > π/2andα θt i ∈[α−δ, π], then the agent will never report typer= 1in roundt. (b) Ifα < π/2andα θt i ∈[0, α+δ], then the agent will never report typer= 2in roundt. (c) Ifα > π/2andα θt i ∈[0, π−α+δ], then the agent will never rep...
-
[11]
Then (a) Ifα > π/2andα θt i ∈(α, π], then the agent will report typer= 2in roundt
Suppose in roundtwe haveθ t =θ p. Then (a) Ifα > π/2andα θt i ∈(α, π], then the agent will report typer= 2in roundt. (b) Ifα < π/2andα θt i ∈[0, α), then the agent will report typer= 1in roundt
-
[12]
Then (a) Ifα > π/2andα θt i ∈(α−δ, α], then the agent will report typer= 1in roundt
Suppose in roundtwe haveθ t =θ p. Then (a) Ifα > π/2andα θt i ∈(α−δ, α], then the agent will report typer= 1in roundt. (b) Ifα < π/2andα θt i ∈[α, α+δ), then the agent will report typer= 2in roundt
-
[14]
Then (a) Ifα θt i ∈[0, α), then the agent will never reportr= 2in roundt
Suppose in roundtwe haveθ t =θ p. Then (a) Ifα θt i ∈[0, α), then the agent will never reportr= 2in roundt. (b) Ifα θt i ∈(α, π], then the agent will never reportr= 1in roundt. Proof of Lemma D.6.We prove Lemma D.6 in Section E.3. When(A1 ′)-(A6′)are satisfied, Algorithm 8 wil...
-
[15]
Ifα bn(s|Θ|−1) i , α bn(s|Θ|) i > π/2, with probability at least1−16⌈logn⌉2· 24(rdδsin)−1/2n−60+80d1/2(δsin)−1/2n−60 π − 2n−4d+3 we havec + 1 >0,c + 2 >0, c+ 1 = 0and c+ 2 = 0
-
[16]
Ifα bn(s|Θ|−1) i , α bn(s|Θ|) i < π/2, with probability at least1−16⌈logn⌉2· 24(rdδsin)−1/2n−60+80d1/2(δsin)−1/2n−60 π − 2n−4d+3 we have c+ 1 >0, c+ 2 >0,c + 1 = 0andc + 2 = 0
-
[17]
Ifα bn(s|Θ|−1) i > π/2andα bn(s|Θ|) i < π/2, then with probability at least1−2n −4d+3 −16⌈logn⌉ 2 · 24(rdδsin)−1/2n−60+80d1/2(δsin)−1/2n−60 π we have(c + 1 >0)∨(c + 2 >0) =True and( c+ 1 >0)∨( c+ 2 >0) = True. 56
-
[18]
Ifα bn(s|Θ|−1) i < π/2andα bn(s|Θ|) i > π/2, then with probability at least1−2n −4d+3 −16⌈logn⌉ 2 · 24(rdδsin)−1/2n−60+80d1/2(δsin)−1/2n−60 π we have(c + 1 >0)∨(c + 2 >0) =True and( c+ 1 >0)∨( c+ 2 >0) = True. Proof of Lemma D.7.In this proof, we assume(A6′)holds for all modif...
-
[19]
The probability that typebn(q1)does not appear in a total number of⌈logn⌉ 4 rounds is upper bounded by(1−f min)⌈logn⌉ 4
Therefore, to havec+ 1 >0, it suffices to show that typebn(q1)appears at least once in a total number of ⌈logn⌉ 4 rounds. The probability that typebn(q1)does not appear in a total number of⌈logn⌉ 4 rounds is upper bounded by(1−f min)⌈logn⌉ 4 . By(A4 ′), we further have 1−(1−f ...
-
[20]
Similarly, we havec+ 2 = 0
As a consequence, we havec+ 1 = 0. Similarly, we havec+ 2 = 0. Next, we prove claim 3. Without loss, we assumes|Θ|−1 =q 1 ands |Θ| =q 2. We consider the modified conditional sector test that outputs(c+ 1 , c− 1 ). By the second claim of Lemma D.6, we see that for this test, wh...
-
[21]
Ifα bn(s|Θ|−1) i , α bn(s|Θ|) i > π/2, with probability at least1−16⌈logn⌉2· 24(rdδsin)−1/2n−60+80d1/2(δsin)−1/2n−60 π − (4i+3⌈log2 n⌉+ 5 +⌈logn⌉)·n −4d+3 , Algorithm 9 implements Algorithm 11, and outputsbα s|Θ|−1 i that satisfies|bα s|Θ|−1 i −α bn(s|Θ|−1) i | ≤4n−4i+3
-
[22]
Ifα bn(s|Θ|−1) i , α bn(s|Θ|) i < π/2, with probability at least1−16⌈logn⌉2· 24(rdδsin)−1/2n−60+80d1/2(δsin)−1/2n−60 π − (4i+3⌈log2 n⌉+ 5 +⌈logn⌉)·n −4d+3 , Algorithm 9 implements Algorithm 12, and outputsbα s|Θ|−1 i that satisfies|bα s|Θ|−1 i −α bn(s|Θ|−1) i | ≤4n−4i+3
-
[23]
Ifα bn(s|Θ|−1) i > π/2andα bn(s|Θ|) i < π/2, then with probability at least1−(4i+3⌈log2 n⌉+ 5 +⌈logn⌉)· n−4d+3 −16⌈logn⌉ 2 · 24(rdδsin)−1/2n−60+80d1/2(δsin)−1/2n−60 π , Algorithm 9 implements Algorithm 10, and outputsbα s|Θ|−1 i that satisfies|bα s|Θ|−1 i −α bn(s|Θ|−1) i | ≤4n−4i+3
-
[24]
Ifα bn(s|Θ|−1) i < π/2andα bn(s|Θ|) i > π/2, then with probability at least1−(4i+3⌈log2 n⌉+ 5 +⌈logn⌉)· n−4d+3 −16⌈logn⌉ 2 · 24(rdδsin)−1/2n−60+80d1/2(δsin)−1/2n−60 π , Algorithm 9 implements Algorithm 10, and outputsbα s|Θ|−1 i that satisfies|bα s|Θ|−1 i −α bn(s|Θ|−1) i | ≤4n...
-
[25]
This implies that the “if” condition in line 4 of Algorithm 11 does not hold for allα−π/2 =u, u+ι,· · ·, u+mιandq∈ {q1, q2}
Therefore, for allα−π/2 =u, u+ι,· · ·, u+mιandq∈ {q 1, q2}, if we run Algorithm 8 with inputs (α, ι, q,bαq (i+1):(d−2),(bαsj i:(d−2))1≤j≤|Θ|−2, n)and observe(c +, c−), thenc − = 0. This implies that the “if” condition in line 4 of Algorithm 11 does not hold for allα−π/2 =u, u+...
-
[26]
In addition, ifα bn(s|Θ|−1) i ∈((u j 1 +u j 2)/2−L j/2,(u j 1 +u j 2)/2)then c− >0, otherwisec − = 0
We then prove by induction that ifα=π/2 +u+ (m+ 1)ιandq=q 1 in line 5, then forj= 1,2,· · ·, J, with probability at least1−4jn−4d+3 , in thej-th round of the while loopα bn(s|Θ|−1) i ∈ ((uj 1 +u j 2)/2−L j/2,(u j 1 +u j 2)/2 +L j/2). In addition, ifα bn(s|Θ|−1) i ∈((u j 1 +u j...
-
[27]
Ifc − = 0in thej-th round of the while loop, thenuj+1 1 = (uj 1 +u j 2)/2andu j+1 2 =u j
By induction,α bn(s|Θ|−1) i ∈((u j 1 +u j 2)/2−L j/2,(u j 1 +u j 2)/2) = (uj+1 2 −L j/2, uj+1 2 ) = ((u j+1 1 +u j+1 2 )/2−L j+1/2,(u j+1 1 +u j+1 2 )/2 +L j+1/2). Ifc − = 0in thej-th round of the while loop, thenuj+1 1 = (uj 1 +u j 2)/2andu j+1 2 =u j
-
[28]
Similar to the proof for the base case, we can show that(A1′)-(A6′)hold for the modified conditional sector test that appears in the (j+ 1)-th round of the while loop
By induction,α bn(s|Θ|−1) i ∈((u j 1 +u j 2)/2,(u j 1 + uj 2)/2 +L j/2) = ((u j+1 1 +u j+1 2 )/2−L j+1/2,(u j+1 1 +u j+1 2 )/2 +L j+1/2). Similar to the proof for the base case, we can show that(A1′)-(A6′)hold for the modified conditional sector test that appears in the (j+ 1)...
-
[29]
In addition, if α bn(s|Θ|−1) i ∈((u j 1 +u j 2)/2−L j/2,(u j 1 +u j 2)/2)thenc + = 0andc − >0, otherwisec + >0
We then prove by induction that ifu1 =π/2 +u+mι,u 2 =π/2 +u+ (m+ 1)ιand w= 1in line 9 of Algorithm 10, then for allj= 1,2,· · ·, J, with probability at least1−4jn−4d+3 , in the j-th round of the while loop we haveα bn(s|Θ|−1) i ∈((u j 1 +u j 2)/2−L j/2,(u j 1 +u j 2)/2 +L j/2)...
-
[30]
Ifc + 2 >0, then for all∆ =u+ι, u+ 2ι,· · ·, u+N1ιwith∆−ι <|α bn(s|Θ|−1) i −π/2|, suppose we run Algorithm 8 with inputs(π/2 + ∆, ι, q2,bαq2 (i+1):(d−2),(bαsj i:(d−2))1≤j≤|Θ|−2, n)and outputs(c +, c−), then with probability at least1−4n −4d+3 we havec + >0
-
[31]
Proof of Lemma D.9.By symmetry, it suffices to prove the first claim
If c+ 1 >0, then for all∆ =u+ι, u+ 2ι,· · ·, u+N1ιwith∆−ι <|α bn(s|Θ|−1) i −π/2|, suppose we run Algorithm 8 with inputs(π/2−∆, ι, q1,bαq1 (i+1):(d−2),(bαsj i:(d−2))1≤j≤|Θ|−2, n)and outputs(c +, c−), then with probability at least1−4n −4d+3 we havec + >0. Proof of Lemma D.9.By...
-
[32]
Here, c∗ := max j∈[|Θ|−1] ⟨ξi+1(α bn(s|Θ|) (i+1):(d−2)), ξi+1(αbn(sj ) (i+1):(d−2))⟩, e∗ := max{−c ∗,0}+ (logn) −1
Ifδ≤min j∈[|Θ|−1] |tan(α bn(sj ) i )| ·(c∗ +e ∗), then whenθt =b n(sj)for somej∈[|Θ| −1], the agent in roundtwill always report typej. Here, c∗ := max j∈[|Θ|−1] ⟨ξi+1(α bn(s|Θ|) (i+1):(d−2)), ξi+1(αbn(sj ) (i+1):(d−2))⟩, e∗ := max{−c ∗,0}+ (logn) −1
-
[33]
Ifx= sign(−α bn(s|Θ|) i +π/2),δ≥ |tan(α bn(s|Θ|) i )| ·(c∗ +e ∗ +n −4i+3.5 ), andθ t =b n(s|Θ|), then the agent in roundtwill report type|Θ|
-
[34]
In the next lemma, we show that the sign ofα bn(s|Θ|) i −π/2can be consistently estimated
Ifx= sign(−α bn(s|Θ|) i +π/2),δ≤ |tan(α bn(s|Θ|) i )| ·(c∗ +e ∗ −n −4i+3.5 ), then the agent in roundtwill never report type|Θ|. In the next lemma, we show that the sign ofα bn(s|Θ|) i −π/2can be consistently estimated. Lemma D.12.Under the conditions of Lemma D.3 withk=|Θ| −1...
-
[35]
For allx∈[−π, π], it holds thatcos(x)≤1−x 2/30
-
[36]
Proof of Lemma E.1.We first look at the first claim
Forx, y, z∈R, ifarc(x, y)≤arc(x, z), then |arc(x, y)−arc(x, z)| ≥cos(x−y)−cos(x−z)≥ (arc(x, y)−arc(x, z))2 30 . Proof of Lemma E.1.We first look at the first claim. By symmetry, it suffices to prove this claim for all x∈[0, π]. DefineF(x) := 1−x 2/30−cos(x). ThenF ′(x) = sin(x...
-
[37]
oracle mechanism
For allx 1, x2 ∈[0, π/2)∪(π/2, π]satisfying|x 1 −π/2| ≥ |x2 −π/2|, it holds that |cos(x 1)| ≤ |cos(x2)| ·|x1 −π/2| |x2 −π/2| . Similarly, forx 1, x2 ∈(0, π)with|x 1 −π/2| ≤ |x2 −π/2|, it holds that 64 Proof of Lemma E.2.To prove the first claim, we simply notice thatcot(π/2) =...
-
[2011]
episodes
adopts the optimism in the face of uncertainty principle to balance the exploration and exploitation trade-off. In specific, the algorithm consists of two major steps: (i) constructing a confidence set containing the true parameterβ∗ using the current data, and (ii) selecting ...
2011
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.