Experimental Design for Semiparametric Bandits

Gi-Soo Kim; Min-hwan Oh; Seok-Jin Kim

REVIEW 2 major objections 5 minor 14 references

Experimental Design for Semiparametric Bandits

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read This paper proves that the unknown common shift in a semiparametric bandit can be handled at no asymptotic cost: the regret matches the linear-bandit minimax rate $\tilde O(\sqrt{dT}\log K)$, with PAC and best-arm guarantees as a byproduct.

desk verdict A genuine advance in semiparametric bandits, but the proof of the headline √dT regret bound has an invalid phase-count step that needs fixing. read the letter →

arxiv 2506.13390 v2 pith:IK6BKRCC submitted 2025-06-16 stat.ML cs.LG

Seok-Jin Kim , Gi-Soo Kim , Min-hwan Oh This is my paper · ORCID

classification stat.MLcs.LG MSC 62K0562L0568T05

keywords semiparametricbanditsorthogonalizedregressionG-optimaldesignregretminimizationbest-armidentificationPACboundsphaseeliminationadversarialshift

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 studies finite-armed bandits where each arm has a feature vector $x_i$, the expected reward is $x_i^\top \theta^\star$ plus an unknown shift $\nu_t$ that can change adversarially every round, and the shift is common to all arms in that round. It aims to establish that this shift costs nothing asymptotically: a phase-elimination algorithm called SBE achieves cumulative regret $\tilde O(\sqrt{dT}\log K)$, matching the minimax lower bound for purely linear bandits even though the model is strictly larger. This is the first $\sqrt d$-rate regret bound for semiparametric bandits, and SBE also returns a PAC learner and a best-arm identifier while running, and gives logarithmic regret when the optimal arm has a positive suboptimality gap, for instance $\tilde O(d\log K/\Delta_\star)$. The reason this is worth caring about is practical: time-varying baselines, trends, and external interference appear in recommendation and clinical settings, and earlier algorithms paid extra factors of $d$.

What carries the argument

The load-bearing mechanism is orthogonalized ridge regression on centered features, together with a two-part design trick. The estimator regresses rewards on $\tilde x_{a_s}=x_{a_s}-\mathbb E[x_{a_s}\mid \mathcal H_{s-1}]$, so the unknown shift $\nu_s$ is absorbed into a martingale difference and cancels in arm comparisons. The DEO design solves the non-convex design problem implicitly: it places half the probability mass on an anchor arm $x_1$ and runs the standard linear G-optimal design on the difference vectors $\{x_i-x_1\}$ with the remaining mass. The identity $\Sigma_p=\sum_{i<j}p_ip_j(x_i-x_j)(x_i-x_j)^\top$ shows the resulting covariance is at least a quarter of the linear design's second moment, giving $\|x_i-x_1\|_{\Sigma_{deo}^{-1}}\le 2\sqrt d$. The sharp statistical rate comes from a decoupling step in Theorem 4: the inverse covariance matrix is separated from the martingale of centered features, so the error is controlled by $\sqrt L/\sqrt t$ rather than by Cauchy-Schwarz's $d/\sqrt t$.

What would settle it

Take the lower-bound instance from Step 5 of Theorem 4: fix any design $p$, set $\nu_s=-\bar{x}_p^\top\theta^\star$ (a legal common shift), and take Gaussian noise, so the reward becomes the linear model $(x_{a_s}-\bar{x}_p)^\top\theta^\star+\eta_s$. Compute the minimax error $\inf_{\hat\theta}\sup_{\theta}|(x_i-x_1)^\top(\hat\theta-\theta^\star)|$ over $t$ samples: the paper's Theorem 4 predicts a rate $\Theta(\sqrt{d}/\sqrt{t})$; if the true rate is $\Theta(d/\sqrt{t})$, the claimed optimal $\sqrt d$ dependence is wrong.

Watch

Extended reading notes

Core claim

The central claim is that the unknown shift $\nu_t$ can be handled without sacrificing the optimal dimension dependence. Because $\nu_t$ is assumed common to all arms in a round, the difference between two arms' expected rewards is $(x_i-x_j)^\top\theta^\star$; the algorithm never needs to estimate $\nu_t$ itself. Orthogonalized regression centers each sampled feature by its conditional mean, $\tilde x_{a_s}=x_{a_s}-\mathbb E[x_{a_s}\mid \mathcal H_{s-1}]$, which turns $\nu_s$ into a martingale term rather than a bias. The paper proves an estimation-error bound for this estimator, $|z^\top(\hat\theta_t-\theta^\star)|=O(\sqrt{L\log(t/\delta)}/\sqrt t + \sqrt{LM}\log(d/\delta)/t)$ with $L=\|z\|_{\Sigma_p^{-1}}^2$ and $M=\max_i\|x_i-\bar x_p\|_{\Sigma_p^{-1}}^2$, attaining the $\sqrt d/\sqrt t$ rate. Combined with the DEO design, whose covariance satisfies $\Sigma_{deo}\succeq \tfrac14 \Sigma_{opt,1}$ so that $\|x_i-x_1\|_{\Sigma_{deo}^{-1}}\le 2\sqrt d$, this yields SBE's $\tilde O(\sqrt{dT}\log K)$ regret, gap-dependent logarithmic regret, and the first PAC and best-arm identification guarantees for semiparametric bandits.

Load-bearing premise

The proof requires the unknown shift to be a single value shared by all arms in each round and fixed before the arm is chosen, so that comparing arms cancels it.

Editorial extensions

If this is right

The common adversarial shift is asymptotically free: SBE's regret has the same order, up to logarithms, as the minimax lower bound for finite-armed linear bandits.
A single algorithm simultaneously minimizes regret, satisfies an $(\epsilon,\delta)$-PAC guarantee with sample complexity $\tilde O(d\log K/\epsilon^2)$, and identifies the best arm in $\tilde O(d\log K/\Delta_\star^2)$ pulls.
When the best arm is separated by a gap $\Delta_\star$, regret becomes logarithmic, of order $\tilde O(d\log K/\Delta_\star)$; exploration effectively stops once the gap is certified.
Applied to $K$ unstructured arms with common time-varying shifts, the method yields $\tilde O(\sqrt{KT})$ regret, matching the multi-armed bandit rate.
The sharp non-asymptotic analysis of orthogonalized regression, which removes the $\sqrt d$ factor that Cauchy-Schwarz arguments leave in the error rate, is a reusable statistical result independent of the bandit framing.

Reading between the lines

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

Inference: The common-shift assumption is the true boundary of the result; if $\nu_t$ were arm-specific, the cancellation $(x_i-x_1)^\top\hat\theta_t$ would fail and regret would plausibly degrade to linear. A testable variant is to add arm-dependent offsets and measure how the regret scales.
Inference: DEO is a generic reduction: any G-optimal design for linear bandits on the difference vectors, mixed with half the mass on an anchor arm, yields a semiparametric design with only a constant-factor loss. This may simplify future algorithms for other semiparametric objectives.
Inference: The decoupling technique used to prove Theorem 4, separating the random inverse covariance from the centered-feature martingale, is transferable to other estimation problems with non-anticipatory shifts, such as offline policy evaluation.
Inference: The MAB application suggests a broader recipe for non-stationary rewards: model the shared time-varying baseline nonparametrically and compare arms through differences, rather than modeling each arm's absolute reward.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Top line: this is a serious paper with a real advance, but the proof of the headline theorem has a gap that needs to be fixed before the result is claimed.

The genuine novelty is the DEO design: shifting features by x_1 and running G-optimal design on the differences reduces the non-convex orthogonalized-regression design problem to a classical one, and Theorem 3 gives the √d bound. Theorem 4's decorrelation argument is the technical heart and is a real improvement over the Cauchy–Schwarz analysis used by all prior work. The PAC and BAI corollaries are new for this model, and the paper is honest about the BAI sample complexity not being instance-optimal. The appendix proofs are detailed and, apart from the issue below, structurally sound.

The problem is in the proof of Theorem 6. Lemma 14 derives a bound with a sum over phases of d/ε_ℓ, which is O(d·2^{L_T}). The proof then replaces that sum by d²L_T, and in D.2 substitutes L_T with the Lemma 15 bound on 2^{L_T}. That substitution is not valid; Lemma 15 says 2^{L_T} ≲ sqrt(T/(d log)), not L_T. Taken literally, Lemma 14 plus Lemma 15 gives d² log(T/d), not √(dT). The claimed rate is recoverable: bound Σ d/ε_ℓ directly by d·2^{L_T} and apply Lemma 15. But as written, the step does not go through. Since Theorem 6 is the paper's headline contribution, this is not a cosmetic typo. The fix is short, and the result is likely correct, but the authors need to redo that part of the proof.

Minor things: the abstract drops the log K factor from the minimax rate (their eO convention explicitly does not hide log K), and Corollary 5 writes τ ≥ ... where it should be τ ≤ ... .

The model assumption that ν_t is a single scalar affecting all arms in a round is explicit and standard in the semiparametric bandit literature. It is a scope limitation—arm-specific shifts would break the centering—but not an unstated one.

Who this is for: bandit theorists, especially anyone working on orthogonalized regression or design-based methods for structured bandits. It deserves a serious referee: the ideas are good, the writing is clear, and the gap is fixable. I would send it out and require the proof correction before acceptance.

Referee Report

2 major / 5 minor

Summary. The paper studies a finite-armed semiparametric bandit model in which the reward of arm i at time t is x_i^T θ* + ν_t + η_t, with ν_t an H_{t-1}-measurable bounded shift common to all arms. The authors introduce an experimental-design procedure (DEO) for orthogonalized regression: put mass 1/2 on an anchor arm and use a G-optimal design on the differences x_i - x_1. They prove a design-cost bound of O(√d) (Theorem 3) and a non-asymptotic estimation error bound whose leading term is √L/√t (Theorem 4), avoiding the previous Cauchy–Schwarz-based bounds. These ingredients are used to give pure-exploration PAC/BAI guarantees and a phase-elimination algorithm SBE with claimed instance-independent regret eO(√dT logK) (Theorem 6), gap-dependent logarithmic regret (Theorem 7), and simultaneous PAC and BAI guarantees (Theorem 8). The appendix contains detailed proofs, including a martingale-based error decomposition for the estimation error.

Significance. If the results hold, this is a substantial advance: it would give the first √d-rate regret bound for semiparametric bandits, matching the finite-armed linear bandit lower bound up to logarithmic factors, and it would be the first work to bring experimental design, PAC, and best-arm-identification guarantees to this model. The DEO design itself is simple and computationally efficient, requiring only O(log T) design computations, and the estimation analysis in Theorem 4 is a genuine improvement over the Cauchy–Schwarz-based arguments used in prior work. The paper is also careful about the dependence on K and about the non-convexity introduced by centering. However, the proof of the headline regret bound contains a specific algebraic gap in the phase-counting step, which directly affects Theorem 6 and also propagates to Theorem 7; the result is likely repairable, but the current text does not derive the claimed rate.

major comments (2)

[Appendix D.1–D.2 (Lemma 14 and proof of Theorem 6)] The phase-counting step in Lemma 14 is invalid. The proof passes from Σ_{ℓ=1}^{L_T} (d log(dKL_T/δ) + dℓ)/ε_ℓ to d²L_T(log(dKL_T/δ)+L_T). Since ε_ℓ = 2^{-ℓ}, the left-hand side contains a geometric sum of order d 2^{L_T}, while the right-hand side replaces 2^{L_T} by dL_T; for L_T modestly large, 2^{L_T} is not bounded by dL_T, and no prior argument establishes such a bound. The subsequent display in D.2 compounds this by substituting √(T/(d log(dK/δ))) for L_T 'by Lemma 15', but Lemma 15 bounds 2^{L_T}, not L_T. Thus the claimed √(dT) regret bound is not derived as written. The gap appears fixable: one can bound the direct sums Σ_ℓ d/ε_ℓ and Σ_ℓ dℓ/ε_ℓ by d·2^{L_T} and d·L_T·2^{L_T}, respectively, and then apply Lemma 15; I recommend rewriting Lemma 14 and D.2 along these lines. After such a repair, the displayed d^{3/2} log(dKT/δ) log(T/d) term in Theorem 6 is not eO(√dT logK) for T comparable to d under the paper's convention that eO hides only logarithmic factors of d and T, so the theorem should either state the required regime or be presented in the min(eO(√dT logK), eO(d√T)) form already discussed in the paper.
[Appendix D.3 (proof of Theorem 7)] The same erroneous replacement appears in the gap-dependent proof. In D.3, the sum Σ_{ℓ=1}^{L⋆} d log(...)/ε_ℓ is again replaced by d²L⋆ log(...), and then d²L⋆ is subsequently replaced by d/Δ⋆ to obtain the final (d/Δ⋆ + d^{3/2})log rate. Neither replacement is justified: the first equates a geometric sum of size 2^{L⋆} ≍ 1/Δ⋆ with L⋆, and the second requires dL⋆ ≍ 1/Δ⋆, which is not true for the definition L⋆ = ⌈log₂(1/Δ⋆)⌉+1 in general. Since Theorem 7 is one of the paper's advertised contributions, this proof step also needs to be corrected.

minor comments (5)

[Abstract and §1.3] The abstract states the minimax regret as eO(√dT), but §1.3 defines eO as hiding only log factors of d and T and not logK, and the introduction and Theorem 6 state eO(√dT logK); the abstract should be made consistent with the convention.
[Corollary 5] The displayed bound says τ(ε,δ) ≥ C₂(...), but the proof derives an upper bound on the number of samples needed; the inequality should be τ(ε,δ) ≤ C₂(...).
[Appendix B, Step 3-2] The bound on ‖Σ_s e_s q_s‖₂ is imported from Lemma 10 of Kim et al. (2021) without stating the lemma; since this is one of the few non-standard ingredients in the proof of Theorem 4, please reproduce its statement or give a self-contained proof so the appendix is complete.
[Appendix H and Theorem 18] The notation for the min of the two sample complexities mixes constants C₂, C₃, and C₄ without a clear definition; the displayed formula in Appendix E and the proof in F.4 should use consistent labels.
[Appendix H and figure captions] There are several typos: 'Compuational Effeiciency' and 'poicy' in Appendix H, and the figure captions mention a 'cosine' shift although the text defines only sine and log shifts; these should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is self-contained; the one overlapping-author concentration lemma is a standard tool, not the claimed result.

full rationale

The derivation chain is not circular. Theorem 3 follows from the external, standard G-optimal design result v* = sqrt(d) applied to the shifted features {x_i - x_1}, combined with the algebraic identity in Lemma 9; no step defines the design in terms of the regret it later yields. Theorem 4 is a genuinely new non-asymptotic estimation-error analysis: the upper bound is obtained by decomposing the orthogonalized-regression error into A, B, and C, controlling A by a decorrelation argument and standard martingale/Bernstein inequalities, with matrix-concentration input from Wang (2023) and a self-normalized martingale lemma from Kim et al. (2021). That latter citation is an overlapping-author work, but it is used only as a technical concentration tool, not as the source of the claimed sqrt(d)-rate or the regret bound, so it does not render the argument circular under the stated rules. The regret, PAC, and BAI results are then derived from Theorems 3 and 4 by a phase-elimination scheme with phase lengths n_ell explicitly chosen from the estimation error bound; no parameter is fitted to data and no quantity later called a prediction is defined in terms of the claimed outcome. The paper also explicitly concedes that its BAI sample complexity is not minimax optimal, which is a limitation rather than a disguised assumption. The skeptic's phase-count concern about the D.2 transition using Lemma 15 is a potential correctness issue in the proof of Theorem 6, not a circularity: a faulty or incomplete algebraic step does not imply that the result was assumed as an input. Overall, the central claims have independent content and the paper is self-contained apart from standard external tools.

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

The paper introduces no fitted free parameters: all constants (1/2 in DEO, the 4C2 in phase lengths, the ridge beta=log(t/delta)) are universal and not tuned to data. It relies on the standard semiparametric bandit model from prior work and external concentration results; no new entities are postulated.

assumptions (6)

domain assumption Bounded parameter, features, shift: ||θ*||₂≤1, ||x_i||₂≤1, |ν_t|≤1 (Assumption 1).
WLOG scaling used throughout; the bounded shift is needed for the martingale bounds on the bias term q_s in Theorem 4.
domain assumption ν_t is arm-invariant and H_{t-1}-measurable (fixed before the action is chosen).
This is the defining property that makes the centered feature \tilde x_{a_s} have conditional mean zero, so orthogonalized regression can cancel the shift; without it the model is different.
domain assumption Noise η_t is independent sub-Gaussian with variance proxy 1.
Needed for Bernstein-type concentration of the reward terms in Theorem 4 and the regret proofs.
domain assumption Action set is finite, fixed, and known, with features spanning R^d.
The phase elimination and G-optimal design require a known finite feasible set; rank reduction is handled WLOG.
standard math Kiefer-Wolfowitz G-optimal design theorem: the minimax prediction variance over any spanning set is √d.
Core to Theorem 3: bounds the DEO design norm by O(√d).
standard math Standard concentration results: Bernstein for real-valued martingales (Fan-Wang 2019), dimension-free Hilbert-space martingale bound (Kim et al. 2021), covariance concentration (Wang 2023, Lemma 26/27).
Technical lemmas used in the proof of Theorem 4; they are established external results.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Experimental Design for Semiparametric Bandits." pith.science (2026). https://pith.science/paper/IK6BKRCC

@misc{pith2026250613390,
  author       = {Pith},
  title        = {Pith review of: Experimental Design for Semiparametric Bandits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IK6BKRCC}},
  note         = {Machine review of arXiv:2506.13390}
}

abstract

We study finite-armed semiparametric bandits, where each arm's reward combines a linear component with an unknown, potentially adversarial shift. This model strictly generalizes classical linear bandits and reflects complexities common in practice. We propose the first experimental-design approach that simultaneously offers a sharp regret bound, a PAC bound, and a best-arm identification guarantee. Our method attains the minimax regret $\tilde{O}(\sqrt{dT})$, matching the known lower bound for finite-armed linear bandits, and further achieves logarithmic regret under a positive suboptimality gap condition. These guarantees follow from our refined non-asymptotic analysis of orthogonalized regression that attains the optimal $\sqrt{d}$ rate, paving the way for robust and efficient learning across a broad class of semiparametric bandit problems.

Figures

Figures reproduced from arXiv: 2506.13390 by the authors.

**Figure 2.** Plots (a) and (b) are the cumulative regret plots of [PITH_FULL_IMAGE:figures/full_fig_p036_2.png] view at source ↗

**Figure 3.** (a), (b) are plots of √ tet for d = 5, K = 30 and d = 30, K = 30. (a) 0 2000 4000 6000 8000 10000 Time 0 5 10 15 20 t * et t * et Over Time_d=5_K=30_log (b) 0 2000 4000 6000 8000 10000 Time 0 10 20 30 40 t * et t * et Over Time_d=30_K=30_log [PITH_FULL_IMAGE:figures/full_fig_p037_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: (a), (b) is plot of √ tet for d = 5, K = 30 and d = 30, K = 30. Appendix J. Technical Lemmas Lemma 24 Assume zi ∼ P i.i.d. for 1 ≤ i ≤ t and define Vb t := Pt i=1 ziz ⊤ i and Vt = tE[z1z ⊤ 1 ]. If ∥zi∥2 ≤ R for some absolute constant R > 0 almost surely, then for β = l…

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 12 canonical work pages

[1]

We then have the following regret bound for this modified algorithm

δεℓ . We then have the following regret bound for this modified algorithm. Theorem 18 (Adaptive regret bound) The adaptive version of SBE has cumulative regret bound Reg(T ) ≲ min eO p dT logK , eO d √ T with probability at least 1− 1 T 2 . Discussion. Our regret bound is robust for the cased≪K. It is strictly sharper than the previous works Kim and Paik ...

work page 2019
[2]

Observe that A := 1 t bΣt +λtId −1 tX s=1 (Σ +λtId) 1 2 (Σ +λtId)− 1 2exasqs = 1 t bΣt +λtId −1(Σ +λtId) 1 2 tX s=1 (Σ +λtId)− 1 2exas| {z } :=es qs := 1 t bΣt +λtId −1(Σ +λtId) 1 2 tX s=1 esqs. Here,es := (Σ +λtId)− 1 2exas∈ Rd is mean zero givenHs−1, and its variance satisfies var(es|H s−1) = (Σ +λtId)− 1 2 E exasex⊤ as|H s−1 (Σ +λtId)− 1 2 = (Σ +λtId)−...

work page 2019
[3]

Pseudo-labeling for kernel ridge regression under covariate shift

Kaizheng Wang. Pseudo-labeling for kernel ridge regression under covariate shift. arXiv preprint arXiv:2302.10160,

arXiv
[4]

We prove the upper bound of the theorem in four steps; afterward, we show its optimality

Also, we have E[exasex⊤ as] = Σ. We prove the upper bound of the theorem in four steps; afterward, we show its optimality. Step 1: Error Decomposition. Using the definition of ˆθt from Eq. (2), decompose the estimation error ˆθt−θ⋆ as ˆθt−θ⋆ = (bVt +βtId)−1 tX s=1 exas(x⊤ asθ⋆ +νs +ηs)− (bVt +βtId)−1bVt +βtId θ⋆ = (bVt +βtId)−1 tX s=1 exas ex⊤ asθ⋆ + ¯x⊤θ...

work page 2013
[6]

(2021)), we aim to bound∥Pt s=1esqs∥2

Next, by applying the dimension-free martingale difference bound (Lemma 10 of Kim et al. (2021)), we aim to bound∥Pt s=1esqs∥2. Since∥qses∥2≤ 2 √ M and E[es|H s−1] = 0, we can bound it with probability at least 1− δ 10: tX s=1 esqs 2 ≲ √ M r t log 10 δ ≲ r tM log 1 δ . Lastly, to bound (Σ +λtId)− 1 2 Σ−bΣt (Σ +λtId)− 1 2 op, we use the result of Lemma 10 ...

work page 2021
[9]

Since T ≳ L(2) T −1X ℓ=1 d2 log(1/δ)4ℓ ≳d2 log(1/δ)4L(2) T , we get the upper bound ofL(2) T as 2L(2) T ≲ s T d2 log(1/δ)

εL(2) T δ L(2) TX ℓ=1 1 εℓ ≲d2 log dL(2) T δ +L(2) T ! L(2) T 2L(2) T . Since T ≳ L(2) T −1X ℓ=1 d2 log(1/δ)4ℓ ≳d2 log(1/δ)4L(2) T , we get the upper bound ofL(2) T as 2L(2) T ≲ s T d2 log(1/δ). Using the above result, we finally get TX t=1 e2(t) ≲d √ T log T d log dT δ = eO(d √ T ). By settingδ = 1 T 2 , it completes the proof. Appendix G. Suboptimality ...

work page 2018
[10]

(2018) and semiparametric-TS of Kim and Paik (2019)

We first simulate the cumulative regret of SBE and compare them with two existing semiparametric bandit algorithms: BOSE from Krishnamurthy et al. (2018) and semiparametric-TS of Kim and Paik (2019). Second, to demonstrate our algorithm is PAC, we examine the maximum estimation error, et := maxi∈[K]|(xi−x1)⊤(ˆθt−θ⋆)| over timet and we plot the value of √ ...

work page 2018
[11]

All previous literature Kim and Paik (2019); Krishnamurthy et al

We constructed feature set with suboptimality gap ∆⋆ = 1/2. All previous literature Kim and Paik (2019); Krishnamurthy et al. (2018) set one parameter as tuning parameter, so we also regard the exploration paramaters as hyperparameters. Hyperparameters. For each algorithm, we tuned a single exploration parameter to its theoretical value, up to a constant ...

work page 2019

Show all 14 references

[13]

We set sameK = 30, but changed = 5 andd = 30 to see the dimension dependency

We run 10 times and plot the error bar. We set sameK = 30, but changed = 5 andd = 30 to see the dimension dependency. The theoretical value is √ tet ≲ eO(√d logK) and we can see the value of √ tet≤ 10√d logK for both cases. Since we calculate every armxi,i∈ [K]’s estimation er...

2000
[14]

(a) 0 2000 4000 6000 8000 10000 Time 0 5 10 15 20t * et t * et Over Time_d=5_K=30_log (b) 0 2000 4000 6000 8000 10000 Time 0 10 20 30 40t * et t * et Over Time_d=30_K=30_log Figure 4: (a), (b) is plot of √ tet ford = 5,K = 30 andd = 30,K =

2000
[30]

We conducted two cases:d = 5,K = 10 andd = 20,K =

(a) 0 2000 4000 6000 8000 10000 12000 14000 Time 0 1000 2000 3000 4000 5000 6000 7000 8000Cumulative Regret Cumulative Regret_d=5_K=10_log Ours (SBE) BOSE Semiparametric-TS (b) 0 5000 10000 15000 20000 25000 30000 Time 0 5000 10000 15000 20000 25000 30000Cumulative Regret Cumu...

2000
[2018]

30 EXPERIMENTAL DESIGN FOR SEMIPARAMETRIC BANDITS The original selection ofβ isβ≍d log(t/δ); however, using Lemma 26, we can relax it for the fixed policy case

Under Assumption 1 (bound- edness), with probability at least 1−δ, the following holds fort: ∥ˆθt−θ⋆∥ bVt+βId ≤ p β + r 27d log 1 + t dδ + 54 log t δ , forβ = log(t/δ) under the fixed policy. 30 EXPERIMENTAL DESIGN FOR SEMIPARAMETRIC BANDITS The original selection ofβ isβ≍d lo...

2018
[2019]

Maximum likelihood estimation is all you need for well-specified covariate shift

Jiawei Ge, Shange Tang, Jianqing Fan, Cong Ma, and Chi Jin. Maximum likelihood estimation is all you need for well-specified covariate shift. arXiv preprint arXiv:2311.15961,

arXiv
[2023]

Gbose: Generalized bandit orthogonalized semiparametric estimation

Mubarrat Chowdhury, Elkhan Ismayilzada, Khalequzzaman Sayem, and Gi-Soo Kim. Gbose: Generalized bandit orthogonalized semiparametric estimation. arXiv preprint arXiv:2301.08781,

arXiv

Pith tools

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

[1] [1]

We then have the following regret bound for this modified algorithm

δεℓ . We then have the following regret bound for this modified algorithm. Theorem 18 (Adaptive regret bound) The adaptive version of SBE has cumulative regret bound Reg(T ) ≲ min eO p dT logK , eO d √ T with probability at least 1− 1 T 2 . Discussion. Our regret bound is robust for the cased≪K. It is strictly sharper than the previous works Kim and Paik ...

work page 2019

[2] [2]

Observe that A := 1 t bΣt +λtId −1 tX s=1 (Σ +λtId) 1 2 (Σ +λtId)− 1 2exasqs = 1 t bΣt +λtId −1(Σ +λtId) 1 2 tX s=1 (Σ +λtId)− 1 2exas| {z } :=es qs := 1 t bΣt +λtId −1(Σ +λtId) 1 2 tX s=1 esqs. Here,es := (Σ +λtId)− 1 2exas∈ Rd is mean zero givenHs−1, and its variance satisfies var(es|H s−1) = (Σ +λtId)− 1 2 E exasex⊤ as|H s−1 (Σ +λtId)− 1 2 = (Σ +λtId)−...

work page 2019

[3] [3]

Pseudo-labeling for kernel ridge regression under covariate shift

Kaizheng Wang. Pseudo-labeling for kernel ridge regression under covariate shift. arXiv preprint arXiv:2302.10160,

arXiv

[4] [4]

We prove the upper bound of the theorem in four steps; afterward, we show its optimality

Also, we have E[exasex⊤ as] = Σ. We prove the upper bound of the theorem in four steps; afterward, we show its optimality. Step 1: Error Decomposition. Using the definition of ˆθt from Eq. (2), decompose the estimation error ˆθt−θ⋆ as ˆθt−θ⋆ = (bVt +βtId)−1 tX s=1 exas(x⊤ asθ⋆ +νs +ηs)− (bVt +βtId)−1bVt +βtId θ⋆ = (bVt +βtId)−1 tX s=1 exas ex⊤ asθ⋆ + ¯x⊤θ...

work page 2013

[5] [6]

(2021)), we aim to bound∥Pt s=1esqs∥2

Next, by applying the dimension-free martingale difference bound (Lemma 10 of Kim et al. (2021)), we aim to bound∥Pt s=1esqs∥2. Since∥qses∥2≤ 2 √ M and E[es|H s−1] = 0, we can bound it with probability at least 1− δ 10: tX s=1 esqs 2 ≲ √ M r t log 10 δ ≲ r tM log 1 δ . Lastly, to bound (Σ +λtId)− 1 2 Σ−bΣt (Σ +λtId)− 1 2 op, we use the result of Lemma 10 ...

work page 2021

[6] [9]

Since T ≳ L(2) T −1X ℓ=1 d2 log(1/δ)4ℓ ≳d2 log(1/δ)4L(2) T , we get the upper bound ofL(2) T as 2L(2) T ≲ s T d2 log(1/δ)

εL(2) T δ L(2) TX ℓ=1 1 εℓ ≲d2 log dL(2) T δ +L(2) T ! L(2) T 2L(2) T . Since T ≳ L(2) T −1X ℓ=1 d2 log(1/δ)4ℓ ≳d2 log(1/δ)4L(2) T , we get the upper bound ofL(2) T as 2L(2) T ≲ s T d2 log(1/δ). Using the above result, we finally get TX t=1 e2(t) ≲d √ T log T d log dT δ = eO(d √ T ). By settingδ = 1 T 2 , it completes the proof. Appendix G. Suboptimality ...

work page 2018

[7] [10]

(2018) and semiparametric-TS of Kim and Paik (2019)

We first simulate the cumulative regret of SBE and compare them with two existing semiparametric bandit algorithms: BOSE from Krishnamurthy et al. (2018) and semiparametric-TS of Kim and Paik (2019). Second, to demonstrate our algorithm is PAC, we examine the maximum estimation error, et := maxi∈[K]|(xi−x1)⊤(ˆθt−θ⋆)| over timet and we plot the value of √ ...

work page 2018

[8] [11]

All previous literature Kim and Paik (2019); Krishnamurthy et al

We constructed feature set with suboptimality gap ∆⋆ = 1/2. All previous literature Kim and Paik (2019); Krishnamurthy et al. (2018) set one parameter as tuning parameter, so we also regard the exploration paramaters as hyperparameters. Hyperparameters. For each algorithm, we tuned a single exploration parameter to its theoretical value, up to a constant ...

work page 2019