Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback

Ruiyuan Huang; Zengfeng Huang

REVIEW 3 major objections 5 minor 13 references

Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback

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

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

Pith's one-line read Cross-learning bandit algorithm claims O~(sqrt(alpha T)) regret, independent of the number of contexts.

desk verdict A plausible self-loop result, overclaimed as covering all strongly observable graphs; the proof's own conclusion contradicts the abstract. read the letter →

arxiv 2502.04678 v2 pith:VV5ZBNFW submitted 2025-02-07 cs.LG

Ruiyuan Huang , Zengfeng Huang This is my paper · ORCID

classification cs.LG MSC 68Q3268T05

keywords cross-learningcontextualbanditsgraphicalfeedbackstronglyobservablegraphsindependencenumberadversarialregretboundsfirst-priceauctionsFTRL

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 tries to settle an open question in cross-learning contextual bandits with graphical feedback: can regret be O~(sqrt(alpha T)), independent of the number of contexts, when contexts are drawn i.i.d. from a fixed distribution? It presents an epoch-based FTRL algorithm that estimates each arm's observation probability from snapshots, builds an importance-weighted loss estimator, and feeds it to a per-context follow-the-regularized-leader update. If correct, the bound matches the minimax regret of ordinary graphical bandits and removes the M-dependence that earlier algorithms could not avoid. The paper states the theorem for all strongly observable graphs, but its own conclusion records that the final graph inequality does not hold when arms lack self-loops and leaves that case open, so the proof as written supports only graphs where every arm is linked to itself.

What carries the argument

The central machinery is an epoch-based importance-weighted estimator with paired time steps. Each epoch fixes a snapshot s_e of the FTRL distribution, defines a target observation probability w_e(a) for every arm, and plays from a mixture q_t that allows rejection sampling to realize w_e(a); half of each paired round estimates the sampling frequency and half estimates losses, producing conditional independence between the pseudo-estimator and the pseudo-distribution used in the analysis. The estimates feed a per-context FTRL subroutine with negative-entropy regularization, and the proof closes with Lemma 3 of Alon et al. (2015), which bounds the sum of w_i/(w_i + sum of in-neighbor weights) by O(alpha log(K/(alpha epsilon))) and is the step that requires self-loops.

What would settle it

Evaluate the key graph sum, sum over arms of w_i/(w_i + sum of in-neighbor weights), on a strongly observable digraph with no self-loops, such as a complete digraph without loops with a weight vector concentrated on one arm; if any instance violates the claimed O(alpha log(K/(alpha epsilon))) bound, the theorem as stated cannot follow from the paper's final step. Alternatively, run the algorithm on that no-self-loop graph and check whether empirical regret tracks O~(sqrt(alpha T)) or grows with the number of contexts.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that adversarial-bandit techniques, run per context and coupled across contexts by the graphical feedback, are enough to remove the context-count dependence. The algorithm plays from a distribution produced by FTRL while a separate snapshot distribution controls how often each arm's loss can be observed; rejection sampling and paired time steps keep the observation indicator nearly independent of the estimator, and an epoch schedule lets the algorithm estimate the unknown context distribution's contribution to each arm's observability. The proof decomposes regret into five terms, bounds each with concentration inequalities, and closes with a graph-theoretic sum bound. The paper also claims the result holds for oblivious adversarial losses, so the stochastic-loss version follows as a corollary. The closing section states that the final graph inequality is not valid without self-loops, which means the full advertised graph class is not covered by the supplied proof.

Load-bearing premise

The proof's last step assumes a known graph inequality holds for every strongly observable graph, but the paper's own conclusion says that inequality fails when arms may lack self-loops, so the proof as written covers only graphs whose arms observe themselves.

Editorial extensions

If this is right

If the theorem holds, the regret no longer depends on the number of contexts, so increasing context resolution does not change the leading-order bound.
Because the losses may be oblivious adversarial rather than stochastic, the stochastic-loss guarantee is a corollary and not the main content.
The O~(sqrt(alpha T)) rate matches the minimax rate for vanilla graphical bandits, so the contextual structure is asymptotically free in this model.
The only graph parameter that enters the bound is the independence number alpha, not the number of arms or contexts.

Reading between the lines

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

Read strictly, the paper's own conclusion limits the proven result to graphs in which every arm has a self-loop; for no-self-loop strongly observable graphs the claimed rate is not established by this proof.
The paired-time-step decoupling of estimation from play is reusable for other partial-feedback structures, since the graph enters the argument mainly through the final inequality on observation probabilities.
For repeated first-price auctions, a direct corollary of the claimed bound would be that the number of private-value types is not a bottleneck at the minimax level, so fine discretization of values should not dominate regret.
A stress test on a no-self-loop strongly observable graph would separate a proof gap from a genuine obstacle: if regret there is empirically worse than O~(sqrt(alpha T)), the missing inequality is substantive.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The paper's real content is an algorithm that achieves O~(sqrt(alpha T)) regret for cross-learning contextual bandits with graphical feedback when the feedback graph has a self-loop at every arm, under stochastic contexts and oblivious adversarial losses. That is a genuine step and would settle the open question for that case. The epoch-based importance estimation adapted from Schneider & Zimmert has plausible machinery, and the known-distribution warm-up is clean. I checked the importance-weighting equality that one reader flagged, and it is fine: conditional on the past, p_{t,c} is fixed, and the indicator's expectation marginalizes to w_t(a) when averaged over the context. So that concern is not real.

The problem is the stated scope. The abstract and Theorem 1 claim coverage of all strongly observable graphs, including arms without self-loops. The proof's final step applies Lemma 3, and the paper's own conclusion says that lemma does not hold for the no-self-loop case and leaves that extension as an open question. That is a direct contradiction. The theorem as stated is not proven; at best it holds for graphs where every arm has a self-loop. The abstract's mention of a 100,000-line Lean formalization and controlled synthetic experiments also has no corresponding section in the body, no repository contents, no commit hash, and no experiment methodology, so those claims are not verifiable from this preprint.

I do not think this is a dishonest paper; the conclusion is candid about the limitation, which makes the abstract overreach more puzzling than malicious. But the mismatch is load-bearing because the no-self-loop case is exactly what the abstract advertises as new.

Who is this for? People working on graphical bandits and cross-learning. The self-loop result itself is worth discussing. But as submitted, no one should cite Theorem 1 as covering no-self-loop graphs.

Recommendation: send it to peer review, but the authors must either shrink the claim to the self-loop case or supply a proof for the missing case. The formalization and experiment claims need to be substantiated or dropped. With the scope corrected, this is a solid paper.

Referee Report

3 major / 5 minor

Summary. The paper studies cross-learning contextual bandits with graphical feedback (Han et al., 2024) under i.i.d. contexts and oblivious adversarial losses. Its main theorem claims that for every strongly observable feedback graph with independence number α, an FTRL-style algorithm with an epoch schedule and a rejection-sampling estimate of observation probabilities achieves expected regret O~(√(αT)), independent of the number of contexts. A shorter analysis for a known context distribution is followed by a longer analysis for unknown ν, with the proof decomposed into five bias/FTRL terms in Appendix B. The paper also reports controlled experiments and claims an end-to-end Lean formalization exceeding 100,000 lines.

Significance. If correct, the result is a significant resolution of an open problem posed by Han et al. (2024) and Wen et al. (2024): it would match the vanilla graphical-bandit rate O~(√(αT)) and remove the polynomial dependence on the number of contexts. The adaptation of the epoch/rejection-sampling technique of Schneider & Zimmert (2023) to graphical feedback is a plausible and interesting strategy, and the claimed Lean formalization and public artifact are notable strengths, provided they are verifiable. However, the paper contains an internal contradiction between the advertised scope and its own conclusion, and the proof has parameter-regime issues. After restricting the result to graphs with self-loops and repairing the parameter conditions, the remaining contribution would still be valuable, but the manuscript as written is not a correct proof of the stated theorem.

major comments (3)

[Abstract and Section 5 (Conclusion)] The abstract explicitly claims coverage of all strongly observable graphs, 'including those with arms without self-loops,' and Theorem 1 is stated for strongly observable graphs. Section 5 says, however, that 'The main problem is that Lemma 3 does not hold for the non-including self-loops case' and 'We leave the extension of our results to the case without self-loops as an interesting open question.' Lemma 3 is exactly the final step in Appendix B that converts the sum ∑_t∑_a p_t(a)/(w_e(a)+γ) into an O~(αT) bound. Therefore the main theorem as stated is not proved; the manuscript must either restrict its scope to graphs in which every arm has a self-loop or supply a replacement graph inequality for the no-self-loop case. This is a load-bearing inconsistency, not a presentation issue.
[Theorem 1 and Lemma 10 (Appendix A)] The parameter choices in Theorem 1 violate the hypothesis of Lemma 10. With L = sqrt(ι α T / log K), γ = 16ι/L, and η = γ/(2(2Lγ+ι)), one has Lγ = 16ι and hence η = 8/(33L), which is larger than (log 2)/(5L) ≈ 0.1386/L. Lemma 10, however, requires η ≤ log(2)/(5L) to conclude that q_t = p_t and that p_t,c(a) is within a constant factor of s_e,c(a) under the event Q. This conclusion is used in bounding bias1, bias3, bias4, and the ftrl term in Appendix B. The proof as written therefore has an invalid parameter regime; the choices of γ and η must be reconciled with Lemma 10.
[Section 3.2 and Lemma 3] The reduction to Lemma 3 is not spelled out correctly. Section 3.2 claims that Lemma 3 shows ∑_t∑_a p_t(a)/w_t(a) = O~(αT), but Lemma 3 as printed bounds ∑_i w_i/(w_i + ∑_{j∈N_in(i)} w_j). Under the paper's definition N_in(a) = {v : v→a}, which includes a itself when a has a self-loop, the denominator in Lemma 3 would count w_i twice, so the two expressions are not the same. The reduction must be made precise, for example by defining the in-neighborhood in Lemma 3 to exclude the vertex itself and taking w_i = p_t(i); otherwise the known-distribution analysis and the final application in Appendix B are not rigorous as written.

minor comments (5)

[Section 1, footnote 2 and Section 5] The definition of strong observability allows arms without self-loops, while Section 5 speaks of 'the assumption that the graph G includes self-loops.' The formal assumptions of Theorem 1 should state explicitly whether self-loops are assumed, to match the proof and the conclusion.
[Algorithm 2 pseudocode] The pseudocode has several formatting errors: the line defining s_{e+1,c_tf}(Nin(a))/(2(L/2)) is difficult to parse, the Bernoulli sampling line is missing a closing parenthesis, and the role of 'RandPerm(t, t+1)' should be explained in the text or pseudocode.
[Appendix B, final bounds] The final display contains '98KTℓ/L', where ℓ should be ι, and a summation variable 'C' is used where 'M' for the number of contexts is intended elsewhere.
[Abstract] The claim of an end-to-end Lean formalization exceeding 100,000 lines is not evidenced in the manuscript; the appendix does not describe the formalization, and a review artifact link alone is not enough for verification. Please provide a description of what is formalized, which theorem statement is checked, and how the artifact can be compiled.
[Section 3.2] In Algorithm 1, the FTRL update writes '- η^{-1} F(x)' while the text defines F(p) = ∑ p_i log p_i; with this sign convention the negative entropy should appear with a plus sign in the argmin, or F should be defined as the negative entropy. The current notation is internally inconsistent.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: parameters are analytic, the proof uses external lemmas, and the no-self-loop scope gap is a correctness issue rather than a circular step.

full rationale

The paper does not fit any parameter to data: eta, gamma, and L are set analytically in terms of T and alpha (Theorem 1). The regret bound is derived by decomposing the regret into five terms (bias1 through bias4 and the FTRL term), bounding each with concentration lemmas that are explicitly stated as extensions of Schneider & Zimmert (2023), and finally applying Lemma 3 (Lemma 5 of Alon et al., 2015), an external graph inequality. The self-citation Huang & Huang (2025) appears only in the Related Work section and is not load-bearing; the proof relies on Schneider & Zimmert (2023) and Alon et al. (2015) as black boxes, which is standard non-circular practice. The paper's own Conclusion states that 'Lemma 3 does not hold for the non-including self-loops case' and leaves the no-self-loop extension open, which contradicts the abstract's claim to cover arms without self-loops. That is a proof-scope inconsistency, not a circular derivation: the theorem is not assumed in its own proof, and no quantity is defined in terms of the target regret bound. Therefore no circular step is present.

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

The central claim rests on standard concentration inequalities and a graph-theoretic lemma from Alon et al. (2015). The paper extends Schneider and Zimmert (2023) to graphical feedback. No new entities are introduced. The main fragility is the domain of validity of Lemma 3, which the paper itself says fails for graphs without self-loops, directly contradicting the abstract's scope.

assumptions (4)

standard math Freedman's inequality (Lemma 2)
Used to derive high-probability concentration bounds throughout Appendix A.
standard math Lemma 3 (Lemma 5 of Alon et al. 2015): for any positive weights with w_i >= epsilon, sum_i w_i/(w_i + sum_{j in N_in(i)} w_j) <= O(alpha log(K/(alpha epsilon)))
The final step of the regret proof applies this lemma to bound sum_t sum_a p_t(a)/(w_t(a)+gamma). The paper's conclusion says this lemma does not hold for graphs without self-loops, which is inconsistent with the theorem statement.
domain assumption The feedback graph G is strongly observable and known to the learner
The algorithm uses the graph structure to define the importance weights and rejection sampling; unknown or non-strongly-observable graphs are outside the claimed scope.
domain assumption Contexts are i.i.d. from a fixed distribution nu; losses are oblivious adversarial
The epoch-based estimation of observation probabilities relies on i.i.d. contexts; the regret decomposition for each fixed context uses the stochastic nature. This is stated in Section 2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback." pith.science (2026). https://pith.science/paper/VV5ZBNFW

@misc{pith2026250204678,
  author       = {Pith},
  title        = {Pith review of: Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VV5ZBNFW}},
  note         = {Machine review of arXiv:2502.04678}
}

abstract

Repeated first-price auctions are contextual decision problems with censored but reusable feedback: after submitting a bid, a learner can infer the outcomes of related bids and evaluate them under different private values. This structure motivates cross-learning contextual bandits with graphical feedback, where playing an arm reveals the losses of its out-neighbors in every context. A central open question was whether, under i.i.d. contexts and a fixed strongly observable feedback graph with independence number $\alpha$, one can remove every polynomial dependence on the number of contexts while attaining the classical graphical-bandit rate $\widetilde O(\sqrt{\alpha T})$. The question was open even for stochastic losses and graphs in which every arm has a self-loop. We answer it affirmatively under the stronger model of oblivious adversarial losses and for all strongly observable graphs, including those with arms without self-loops. The key obstruction is that a frequently played no-self-loop arm can nevertheless have a vanishing observation probability. Our algorithm isolates one such arm per epoch, uses a pessimistic correction to cancel its first-order estimation drift, and shifts the losses in the FTRL analysis to control the resulting quadratic term. It achieves expected regret $\widetilde O(\sqrt{\alpha T})$. Controlled synthetic experiments show the benefit of combining graph feedback with cross-learning and exhibit the predicted scaling in both $T$ and $\alpha$. The main theorem is formalized in Lean in an end-to-end development exceeding 100,000 lines of Lean code. The formalization and experiment artifacts are available in the GitHub repository: https://github.com/RuiyuanHuang/graphical-cross-learning-review-artifact.

Figures

Figures reproduced from arXiv: 2502.04678 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 10 canonical work pages

[1]

Lemma 3 (Lemma 5, Alon et al

Then, with probability at least 1− δ, we have for all t, t∑ s=1 Xs− µs≤ λ t∑ s=1 Vs + log(1/δ) λ . Lemma 3 (Lemma 5, Alon et al. (2015) ) . Let G = ( V, E) be a directed graph with |V| = K, in which each node i∈ V is assigned a positive weight wi. Assume that ∑ i∈V wi≤ 1, and that wi≥ ǫ for all i∈ V for some constant 0 < ǫ < 1 2 . Then ∑ i∈V wi wi +∑ j∈N ...

work page 2015
[5]

Wang, Q., Y ang, Z., Deng, X., and Kong, Y

doi: 10.1214/14-STS504. Wang, Q., Y ang, Z., Deng, X., and Kong, Y . Learning to bid in re peated ﬁrst-price auctions with budgets. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and S carlett, J. (eds.), Proceedings of the 40th International Conference on Machine Learning , volume 202 of Proceedings of Machine Learning Research , pp. ...

doi:10.1214/14-sts504
[8]

By the previous two lemmas, it is easy to see that Pr(Q)≥ 1− 3K(T /L) exp(−ι)

Let Q be the indicator of the event that all previous events we and Le hold Q = ∏ e weLe. By the previous two lemmas, it is easy to see that Pr(Q)≥ 1− 3K(T /L) exp(−ι). For each epoch e and arm a, we consider the following ratio βe(a) = we(a) + γ ˆwe(a) + 3 2 γ . For this ratio, we have the following lemma. Lemma 9 (Extensions of Lemma 8 in Schneider & Zi...

work page 2023
[9]

The ﬁrst sequence of indicator variables {Fe} represents the concentration of our empirical importance ˆwe(a) around the expected importance we(a)

For each epoch e, we deﬁne the following two indicator variables: Fe ≜ /BD ( ∀a,|ˆwe(a)− we(a)|≤ 2 max {√ we(a)ι L , ι L }) and Le ≜ /BD ( max c∈[M],a∈[K] ∑ t∈T e ~ℓt,c(a)≤ L + ι γ ) . The ﬁrst sequence of indicator variables {Fe} represents the concentration of our empirical importance ˆwe(a) around the expected importance we(a). The second sequence of i...

work page 2023
[10]

18 ARXIV PREPRINT - F EBRUARY 10, 2025 Bounding bias4. We have bias4 =E [ ∑ e ∑ t∈T e ⟨ pt,ct−~pt,ct,~ℓt,ct−ˆℓt,ct ⟩] =E [ ∑ e ∑ t∈T e ⟨ pt,ct−~pt,ct,~ℓt,ct−ˆℓt,ct ⟩ Q ] + E [ ∑ e ∑ t∈T e ⟨ pt,ct−~pt,ct,~ℓt,ct−ˆℓt,ct ⟩ (1− Q) ] ≤E [ ∑ e ∑ t∈T e ⟨ pt,ct−~pt,ct,~ℓt,ct−ˆℓt,ct ⟩ Q ] + (1− Pr(Q)) 2 γ =E   T /L∑ e=1 ∑ t∈Te K∑ a=1 (pt,ct (a)−~pt,ct(a))(1− βe(a...

work page 2025
[11]

We bound those terms separately

We decompose the re gret as Reg(π) = E [ T∑ t=1 ⟨qt,ct− πct , ℓt,ct⟩ ] = E [ T∑ t=1 ⟨qt,ct− pt,ct, ℓt,ct⟩ ] /bracehtipupleft /bracehtipdownright/bracehtipdownleft/bracehtipupright bias1 + E [ T∑ t=1 ⟨ pt,ct− πct, ℓt,ct−~ℓt,ct ⟩] /bracehtipupleft /bracehtipdownright/bracehtipdownleft/bracehtipupright bias2 + E [ T∑ t=1 ⟨ ~pt,ct− πct,~ℓt,ct−ˆℓt,ct ⟩] /brace...

work page 2025
[13]

19 ARXIV PREPRINT - F EBRUARY 10, 2025 Combining the pieces together. We have Reg(π) = bias1 + bias2 + bias3 + bias4 + ftrl ≤ (1− Pr(Q)) T + γE   T∑ t=1 ∑ a∈[K] pt(a) we(a) + γ   + 4γE   T∑ t=1 ∑ a∈[K] pt(a) we(a) + γ   + T (1− Pr(Q)) 2 γ + ( 98ι L + γ2L ι )E   T∑ t=1 ∑ a∈[K] pt(a) we(a) + γ   + (1− Pr(Q)) 2 γ + 4ηE   T∑ t=1 ∑ a∈[K] pt(a) we...

work page 2025
[2010]

ISBN 9781605587998

Association for Computing Machinery. ISBN 9781605587998. doi: 10.1145/1772690.1772758. Luo, H., Tong, H., Zhang, M., and Zhang, Y . Improved high-pro bability regret for adversarial bandits with time- varying feedback graphs. In Agrawal, S. and Orabona, F. (eds .), Proceedings of The 34th International Confer- ence on Algorithmic Learning Theory , volume ...

work page arXiv

Show all 13 references

[2015]

and Zimmert, J

Schneider, J. and Zimmert, J. Optimal cross-learning for co ntextual bandits with unknown context distributions. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., an d Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 51862–51880....

2023
[2019]

Understanding band its with graph feedback

10 ARXIV PREPRINT - F EBRUARY 10, 2025 Chen, H., Huang, z., Li, S., and Zhang, C. Understanding band its with graph feedback. In Ranzato, M., Beygelz- imer, A., Dauphin, Y ., Liang, P ., and V aughan, J. W . (eds.), Advances in Neural Information Processing Systems , volume 34...

2025
[2021]

Learning to bid optimally and efﬁciently in adversarial ﬁrst-price auctions

Han, Y ., Zhou, Z., Flores, A., Ordentlich, E., and Weissman,T. Learning to bid optimally and efﬁciently in adversarial ﬁrst-price auctions. ArXiv, abs/2007.04568,

2007
[2023]

Stochastic contextual banditswith graph feedback: from independence number to mas number

Wen, Y ., Han, Y ., and Zhou, Z. Stochastic contextual banditswith graph feedback: from independence number to mas number. arXiv preprint arXiv:2402.18591 ,

arXiv
[2024]

Lemma 2 (Freedman’s Inequality)

11 ARXIV PREPRINT - F EBRUARY 10, 2025 A Useful Deﬁnitions and Lemmas We list some useful deﬁnitions and lemmas here. Lemma 2 (Freedman’s Inequality) . Fix any λ > 0 and δ∈ (0, 1). Let Xt be a random process with respect to a ﬁltration Ft such that µt = E [Xt|F t−1] and Vt = E...

2025

Pith tools

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

[1] [1]

Lemma 3 (Lemma 5, Alon et al

Then, with probability at least 1− δ, we have for all t, t∑ s=1 Xs− µs≤ λ t∑ s=1 Vs + log(1/δ) λ . Lemma 3 (Lemma 5, Alon et al. (2015) ) . Let G = ( V, E) be a directed graph with |V| = K, in which each node i∈ V is assigned a positive weight wi. Assume that ∑ i∈V wi≤ 1, and that wi≥ ǫ for all i∈ V for some constant 0 < ǫ < 1 2 . Then ∑ i∈V wi wi +∑ j∈N ...

work page 2015

[2] [5]

Wang, Q., Y ang, Z., Deng, X., and Kong, Y

doi: 10.1214/14-STS504. Wang, Q., Y ang, Z., Deng, X., and Kong, Y . Learning to bid in re peated ﬁrst-price auctions with budgets. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and S carlett, J. (eds.), Proceedings of the 40th International Conference on Machine Learning , volume 202 of Proceedings of Machine Learning Research , pp. ...

doi:10.1214/14-sts504

[3] [8]

By the previous two lemmas, it is easy to see that Pr(Q)≥ 1− 3K(T /L) exp(−ι)

Let Q be the indicator of the event that all previous events we and Le hold Q = ∏ e weLe. By the previous two lemmas, it is easy to see that Pr(Q)≥ 1− 3K(T /L) exp(−ι). For each epoch e and arm a, we consider the following ratio βe(a) = we(a) + γ ˆwe(a) + 3 2 γ . For this ratio, we have the following lemma. Lemma 9 (Extensions of Lemma 8 in Schneider & Zi...

work page 2023

[4] [9]

The ﬁrst sequence of indicator variables {Fe} represents the concentration of our empirical importance ˆwe(a) around the expected importance we(a)

For each epoch e, we deﬁne the following two indicator variables: Fe ≜ /BD ( ∀a,|ˆwe(a)− we(a)|≤ 2 max {√ we(a)ι L , ι L }) and Le ≜ /BD ( max c∈[M],a∈[K] ∑ t∈T e ~ℓt,c(a)≤ L + ι γ ) . The ﬁrst sequence of indicator variables {Fe} represents the concentration of our empirical importance ˆwe(a) around the expected importance we(a). The second sequence of i...

work page 2023

[5] [10]

18 ARXIV PREPRINT - F EBRUARY 10, 2025 Bounding bias4. We have bias4 =E [ ∑ e ∑ t∈T e ⟨ pt,ct−~pt,ct,~ℓt,ct−ˆℓt,ct ⟩] =E [ ∑ e ∑ t∈T e ⟨ pt,ct−~pt,ct,~ℓt,ct−ˆℓt,ct ⟩ Q ] + E [ ∑ e ∑ t∈T e ⟨ pt,ct−~pt,ct,~ℓt,ct−ˆℓt,ct ⟩ (1− Q) ] ≤E [ ∑ e ∑ t∈T e ⟨ pt,ct−~pt,ct,~ℓt,ct−ˆℓt,ct ⟩ Q ] + (1− Pr(Q)) 2 γ =E   T /L∑ e=1 ∑ t∈Te K∑ a=1 (pt,ct (a)−~pt,ct(a))(1− βe(a...

work page 2025

[6] [11]

We bound those terms separately

We decompose the re gret as Reg(π) = E [ T∑ t=1 ⟨qt,ct− πct , ℓt,ct⟩ ] = E [ T∑ t=1 ⟨qt,ct− pt,ct, ℓt,ct⟩ ] /bracehtipupleft /bracehtipdownright/bracehtipdownleft/bracehtipupright bias1 + E [ T∑ t=1 ⟨ pt,ct− πct, ℓt,ct−~ℓt,ct ⟩] /bracehtipupleft /bracehtipdownright/bracehtipdownleft/bracehtipupright bias2 + E [ T∑ t=1 ⟨ ~pt,ct− πct,~ℓt,ct−ˆℓt,ct ⟩] /brace...

work page 2025

[7] [13]

19 ARXIV PREPRINT - F EBRUARY 10, 2025 Combining the pieces together. We have Reg(π) = bias1 + bias2 + bias3 + bias4 + ftrl ≤ (1− Pr(Q)) T + γE   T∑ t=1 ∑ a∈[K] pt(a) we(a) + γ   + 4γE   T∑ t=1 ∑ a∈[K] pt(a) we(a) + γ   + T (1− Pr(Q)) 2 γ + ( 98ι L + γ2L ι )E   T∑ t=1 ∑ a∈[K] pt(a) we(a) + γ   + (1− Pr(Q)) 2 γ + 4ηE   T∑ t=1 ∑ a∈[K] pt(a) we...

work page 2025

[8] [2010]

ISBN 9781605587998

Association for Computing Machinery. ISBN 9781605587998. doi: 10.1145/1772690.1772758. Luo, H., Tong, H., Zhang, M., and Zhang, Y . Improved high-pro bability regret for adversarial bandits with time- varying feedback graphs. In Agrawal, S. and Orabona, F. (eds .), Proceedings of The 34th International Confer- ence on Algorithmic Learning Theory , volume ...

work page arXiv