Pith. sign in

REVIEW 4 major objections 4 minor 64 references

Federated Linear Dueling Bandits

T0 review · 4 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read The paper proves that multiple agents solving contextual linear dueling bandits can collaborate by exchanging only gradients—not raw arm or feedback data—and that the resulting online-gradient-descent algorithm has cumulative regret that…

desk verdict Good algorithm, flawed proofs: the main regret bounds rely on a false inequality and a false identity, so the paper needs a major revision. read the letter →

arxiv 2502.01085 v2 pith:OAQHYXHH submitted 2025-02-03 cs.LG

Xuhan Huang , Yan Hu , Zhiyan Li , Zhiyong Wang , Benyou Wang , Zhongxiang Dai This is my paper · ORCID
classification cs.LG
keywords federatedlearningduelingbanditslinearonlinegradientdescentcumulativeregretcommunicationefficiencylogisticpreferencemodelfeedback
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

Many preference-learning applications, from recommender systems to LLM response ranking, fit the dueling-bandit model: each round an agent picks a pair of options and sees a relative preference. Existing algorithms handle a single agent, and previous federated bandit methods do not transfer because the linear dueling estimator has no closed-form update. This paper tries to establish that collaboration can still be achieved by writing the joint estimation loss as a sum of per-agent losses and exchanging local gradients rather than raw data. The proposed FLDB-OGD algorithm runs one projected online gradient descent step every $\tau$ iterations and is proven to achieve sublinear cumulative regret, with a regret–communication trade-off controlled by $\tau$. If the proof is right, it gives a practical way for many agents to jointly learn preferences while keeping their data local.

What carries the argument

The central object is the per-round federated loss $f_s^{\mathrm{fed}}(\theta')=\sum_{i=1}^N l_s^i(\theta')$ (with a regularization term only at $s=1$), whose gradient decouples into a sum of agents' local gradients. Around this, FLDB-OGD builds a projected online gradient descent routine: after every $\tau$ rounds the server sums the newly collected local gradients, takes one step of size $\eta=1/(\alpha t_c)$, and projects back onto a ball of radius $r$ centered at the current iterate. The argument's load-bearing property is $\alpha$-strong convexity of each $f_s^{\mathrm{fed}}$ on that ball, which Proposition 4.4 guarantees when the number of agents satisfies $N \ge \left((C_1\sqrt{d}+C_2\sqrt{\log(2/\delta)})/\lambda_f\right)^2 + 2\alpha/(\kappa_\mu\lambda_f)$; Lemma 4.5 then controls the distance between the averaged online estimate and the true maximum-likelihood estimate, and a self-normalized concentration inequality converts that parameter error into the regret bound.

What would settle it

Sample arm sets from a distribution whose feature differences are concentrated in a low-dimensional subspace, so $\lambda_{\min}(\mathbb{E}[\tilde{\phi}\tilde{\phi}^\top])=0$ and $\lambda_f=0$, then run FLDB-OGD with a small number of agents; the cumulative regret should stop being sublinear if the paper's condition is truly needed. Concretely, estimate $\lambda_{\min}(\mathbb{E}[\tilde{\phi}\tilde{\phi}^\top])$ from the arm distribution and compare the agent count $N$ with the threshold in Proposition 4.4.

Watch

Extended reading notes

Core claim

FLDB-OGD estimates the shared linear parameter $\theta$ by minimizing the federated loss $L_t^{\mathrm{fed}}(\theta') = \sum_{i=1}^N L_t^i(\theta') + \frac{\lambda}{2}\|\theta'\|_2^2$, whose gradient is the sum of the agents' local gradients. A central server aggregates these gradients, takes one projected online gradient descent step with step size $\eta_{t_c}=1/(\alpha t_c)$, and broadcasts both the averaged iterate $\tilde{\theta}(t_c+1)=\frac{1}{t_c+1}\sum_{j=1}^{t_c+1}\hat{\theta}(j)$ and the aggregated information matrix $W_{\mathrm{sync}}$. The paper proves that, with probability at least $1-\delta$, the cumulative regret over all N agents and T rounds is $\tilde{O}\left(N d + \frac{d}{\kappa_\mu}\sqrt{T} + \frac{N^{3/2}\sqrt{d}}{\alpha}\sqrt{T}\right)$ when $\tau=1$, and $\tilde{O}\left(\tau N d + \frac{d\sqrt{\tau}}{\kappa_\mu}\sqrt{T} + \frac{\tau N^{3/2}\sqrt{d}}{\alpha}\sqrt{T}\right)$ for general $\tau>1$. The $\tau$-dependent formula is the paper's claimed regret–communication trade-off, while the $\tau=1$ bound shows that even one gradient exchange per round suffices for a sublinear cumulative regret.

Load-bearing premise

The proof's engine—the per-round loss being strongly convex—is guaranteed only when the number of agents is large enough relative to an unknown distributional constant $\lambda_f$, which describes how thoroughly the arm feature differences span every direction; the experiments never verify this condition.

Editorial extensions

If this is right

  • FLDB-OGD is the first federated linear dueling bandit algorithm with a sublinear regret guarantee; it needs only one communication round per $\tau$ iterations.
  • Increasing $\tau$ makes the regret bound worse—roughly a factor $\tau$ on the agent-dependent terms and $\sqrt{\tau}$ on the horizon term—while reducing communication rounds by a factor $\tau$, giving an explicit knob rather than a fixed cost.
  • For the full-gradient version FLDB-GD, the bound improves as the number of agents $N$ grows, so collaboration provably lowers per-agent regret in the idealized no-communication-cost regime.
  • With $N=1$ the FLDB-GD guarantee reduces to the classical linear dueling bandit order, so the federated construction preserves the single-agent baseline.

Reading between the lines

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

  • The same 'sum of local losses implies sum of local gradients' mechanism is not specific to linear models; it could extend the algorithm to kernelized or neural dueling bandits, which the paper lists as future work.
  • The theory's dependence on $\lambda_f$ implies a threshold effect in $N$ that the experiments do not probe; estimating $\lambda_{\min}(\mathbb{E}[\tilde{\phi}\tilde{\phi}^\top])$ from the arm distribution would let practitioners check whether they are in the provable regime.
  • Sharing gradients is not by itself a privacy guarantee; applying standard differential-privacy noise to the communicated gradients would create a new accuracy–privacy trade-off, a direction the paper does not analyze.
  • The empirical finding that larger $N$ always helps FLDB-OGD sits outside the stated bound's $N$-independent (or $N$-worsening) terms; making the gradient-norm bound $N$-independent would close this gap, as the paper itself suggests.
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

4 major / 4 minor

Summary. The paper introduces two federated algorithms for contextual linear dueling bandits: FLDB-GD, a vanilla method that performs multiple rounds of federated gradient descent per iteration, and FLDB-OGD, a communication-efficient variant that performs one online gradient descent step after every τ iterations. The authors claim sublinear cumulative regret bounds for both algorithms, with FLDB-OGD exhibiting a regret--communication trade-off controlled by τ. They support these claims with analyses in Section 4 and appendices, and with synthetic and MovieLens experiments in Section 5. The core theoretical contribution is the bound in Theorem 4.6 for FLDB-OGD with τ=1 and its extension in Proposition 4.7 to τ>1, both of which rely on Lemma 4.5 and its proof in Appendix E.

Significance. If the theoretical results were correct, the paper would make a useful contribution by extending federated bandit learning to the dueling-bandit setting, where parameter estimates lack closed forms. The algorithmic idea of exchanging gradients for the dueling-bandit loss, rather than sufficient statistics, is plausible and goes beyond prior federated linear bandit work. The empirical study is reasonably extensive and illustrates the intended benefits of collaboration and the communication--regret trade-off. However, the correctness of the central regret bounds is not established: the proof of Lemma 4.5 contains a false inequality, the proof of Lemma 4.2 in the FLDB-GD analysis contains a false identity, and the reduction in Proposition 4.7 is not valid as written. These are load-bearing errors, so the theoretical contribution currently does not stand.

major comments (4)
  1. [Appendix E, Eq. (31)] The inequality ∑_{s=1}^t f_s^fed(θhat(s)) ≥ ∑_{s=1}^t f_s^fed(θtilde(t)) is asserted to follow from Jensen's inequality, but it is false for general convex functions. Jensen gives f_s(θtilde(t)) ≤ (1/t)∑_{j=1}^t f_s(θhat(j)) for each fixed s, which does not imply the displayed inequality. A concrete counterexample is f_1(x)=x^2, f_2(x)=(x-10)^2, θhat(1)=0, θhat(2)=10, θtilde(2)=5, for which the left-hand side is 0 and the right-hand side is 50. This inequality is used to transfer the OGD regret bound on ∑_s(f_s^fed(θhat(s)) - f_s^fed(θ_t)) to ∑_s(f_s^fed(θtilde(t)) - f_s^fed(θ_t)); without this transfer, the strong-convexity argument in (33)--(35) cannot yield ||θtilde(t)-θ_t|| ≤ (N/α)√((1+log t)/t), and Lemma 4.5 fails. Since Theorem 4.6 and Proposition 4.7 both rely on Lemma 4.5, the paper's central sublinear-regret claim for FLDB-OGD is not established.
  2. [Appendix C] The proof repeatedly uses the identity G_t(θ)=0, but from the definition G_t(θ') = ∑_{s=1}^t (μ(θ'^T φ_s) - μ(θ^T φ_s)) φ_s + λθ', evaluating at θ'=θ gives G_t(θ)=λθ, which is not zero in general. The subsequent derivation of (11), which is used to bound ||θ-θ_t||_{V_t} and to prove Lemma 4.2, relies on this false identity. This affects the regret bound for FLDB-GD in Theorem 4.3.
  3. [Appendix G] The reduction of the τ>1 case to 'Nτ agents with a local update period of 1' is not a valid substitution into the τ=1 bound. With τ>1, each communication round aggregates Nτ per-observation gradients but performs one OGD step with step size η_{t_c}=1/(α t_c); the per-round loss is a sum of τ per-iteration losses and is therefore τα-strongly convex if each per-iteration sum is α-strongly convex. Substituting N'=Nτ and T'=T/τ into Theorem 4.6 without adjusting α gives d√T' = d√(T/τ) for the middle term, not d√τ √T as written in (8). Even granting the equivalence, the stated τ-dependence in (8) does not follow from the reduction.
  4. [Appendix E, proof of Proposition 4.4] The proof states that 'since we update θtilde_t every N rounds, for the next N rounds the pulled arms are only dependent on θtilde_t', but in the τ=1 case (the setting of Theorem 4.6 and the use of Proposition 4.4 in Lemma 4.5) θtilde_t is updated every round, so the feature vectors are not IID over the next N rounds. The argument should instead invoke Proposition E.2 on the N agents' feature differences within a single round, conditional on the current θtilde_t. As written, the strong-convexity conclusion is not justified.
minor comments (4)
  1. [Algorithm 1] Line 8 uses θhat, but the pseudocode initialization in line 1 does not define θhat; the text explains in Section 3.2 that θhat(1) is set at t=1, but the pseudocode should include this initialization for completeness.
  2. [Section 3.2] The notation f_{t_c}^fed in Algorithm 2 line 3 aggregates gradients over the last τ iterations, whereas f_s^fed in Eq. (4) is defined per iteration; the relationship between these two objects should be stated explicitly to avoid confusion.
  3. [Section 4.2] The discussion of the gradient bound G says 'if we additionally assume that there exists an upper bound G on expected gradient norm which is independent of N', but no such assumption is formalized or used in a theorem; consider stating it as a corollary or a separate assumption.
  4. [Appendix B] The experiments report means over three independent runs; with only three seeds, the error bars are not very informative, and the empirical claims would be stronger with more seeds.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: FLDB-OGD's regret analysis is self-contained and no prediction reduces by construction to a fit or to a self-citation.

full rationale

The central derivation is not circular. The regret bounds in Theorem 4.6 and Proposition 4.7 are built from Lemma 4.2 (a concentration inequality for the MLE-style minimizer θt, proved via Theorem 1 of Abbasi-Yadkori et al.), Proposition 4.4 (α-strong convexity obtained from Assumption 2.2 and Proposition 1 of Li et al. with an explicit lower bound on N), Lemma 4.5 (transferring an OGD regret bound from Hazan's textbook to θ̃(t)), and standard sum-of-norms control of the arm-feature covariance. None of these inputs is defined in terms of the regret bound being proved, and no parameter is fitted to the empirical curves to make the theorem match the experiments. The α in Proposition 4.4 is chosen as a constant with a matching N-dependence, not calibrated from data, and the τ > 1 bound in Proposition 4.7 is obtained by the stated reduction to the τ = 1 case rather than by importing an equivalent conclusion. The paper does contain self-citations by co-authors (e.g., [6], [12], [57]), but they occur in motivation and related work and do not carry the load of the regret proof. A separate concern is that inequality (31) in Appendix E is not implied by Jensen's inequality and appears mathematically false; however, that is a proof-correctness defect, not a circularity, because the claimed inequality is not equivalent to the theorem's inputs by construction. The diversity assumption (Assumption 2.2) and the strong-convexity condition in Proposition 4.4 are substantial stated assumptions, but assuming a condition is not circular reasoning.

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

The analysis imports standard bandit assumptions, an exact MLE idealization for FLDB-GD, and a distributional diversity condition; no new physical or conceptual entities are postulated.

free parameters (4)
  • λ (regularization coefficient) = 1/T in experiments
    Regularization strength in the MLE loss (Eq. 1); appears in the regret bounds and in the confidence ball radius in Lemma E.1. Chosen by hand, not fitted to data.
  • α (strong convexity parameter) = 1000 in experiments
    Strong-convexity constant and OGD step-size denominator (Algorithm 2, line 4). The regret bound in Thm 4.6 scales inversely with α; in experiments it is set to 1000.
  • τ (communication period) = varied 1 to 8, default 1
    Communication period. Prop 4.7 shows regret grows with τ while communication rounds drop by 1/τ; this is the tunable knob of the trade-off.
  • M (number of federated GD rounds in FLDB-GD) = unspecified
    Number of gradient-exchange rounds per iteration in FLDB-GD. Assumption 4.1 says M steps exactly minimize the global loss, but no M is given or bounded.
assumptions (5)
  • domain assumption BTL preference model with logistic link and linear reward f(x)=θ^T φ(x)
    Sec 2 defines this as the problem setting; restricts to linear realizability.
  • domain assumption Assumption 2.1: κμ > 0, Lipschitz link, bounded feature differences
    Sec 2; standard but nontrivial, especially κμ > 0 for logistic on unbounded inputs.
  • domain assumption Assumption 2.2: diversity λf > 0 for the feature-difference covariance under the algorithm's own selection rule
    Sec 2; ensures no blind spots, but is not verified and depends on the algorithm's exploration bonus.
  • ad hoc to paper Assumption 4.1: after M rounds of federated GD, θsync exactly minimizes the global loss
    Sec 4.1; only true in the limit M→∞, and the paper admits it may require a large number of communication rounds.
  • standard math External propositions: Prop E.2 of [17] (minimum eigenvalue concentration) and Theorem 3.3 of [60] (OGD regret for strongly convex functions)
    Used as black boxes in Appendices E; not proved in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Federated Linear Dueling Bandits." pith.science (2026). https://pith.science/paper/OAQHYXHH

@misc{pith2026250201085,
  author       = {Pith},
  title        = {Pith review of: Federated Linear Dueling Bandits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OAQHYXHH}},
  note         = {Machine review of arXiv:2502.01085}
}
read the original abstract

Contextual linear dueling bandits have recently garnered significant attention due to their widespread applications in important domains such as recommender systems and large language models. Classical dueling bandit algorithms are typically only applicable to a single agent. However, many applications of dueling bandits involve multiple agents who wish to collaborate for improved performance yet are unwilling to share their data. This motivates us to draw inspirations from federated learning, which involves multiple agents aiming to collaboratively train their neural networks via gradient descent (GD) without sharing their raw data. Previous works have developed federated linear bandit algorithms which rely on closed-form updates of the bandit parameters (e.g., the linear function parameters) to achieve collaboration. However, in linear dueling bandits, the linear function parameters lack a closed-form expression and their estimation requires minimizing a loss function. This renders these previous methods inapplicable. In this work, we overcome this challenge through an innovative and principled combination of online gradient descent (OGD, for minimizing the loss function to estimate the linear function parameters) and federated learning, hence introducing our federated linear dueling bandit with OGD (FLDB-OGD) algorithm. Through rigorous theoretical analysis, we prove that FLDB-OGD enjoys a sub-linear upper bound on its cumulative regret and demonstrate a theoretical trade-off between regret and communication complexity. We conduct empirical experiments to demonstrate the effectiveness of FLDB-OGD and reveal valuable insights, such as the benefit of a larger number of agents, the regret-communication trade-off, among others.

Figures

Figures reproduced from arXiv: 2502.01085 by the authors.

Figure 1
Figure 1. Cumulative regret for different methods with varying numbers of agents: (a) [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Cumulative regret of FLDB-OGD under different settings. (a)–(b): Impact of the number of agents with K = 10, 50 and d = 5. (c): Performance under heterogeneous rewards with K = 5, d = 5. (d): Final regret versus number of communication rounds with N = 100, d = 5. term in Theorem 4.6 can be replaced by G √ N √ d α √ T. This would then make our average regret upper bound (averaged over N agents) become tighter with a … view at source ↗
Figure 3
Figure 3. Cumulative regret with varying σ 2 under K = 5, d = 5. The results for the experiments with heterogeneous rewards are shown in [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Cumulative regret with varying τ under N = 100, K = 10, d = 5. 1 2 3 4 5 6 7 8 Update Period ( ) 40 50 60 70 80 90 Final Cumulative Regret FLDB-OGD (K=5) FLDB-OGD (K=10) 100 200 300 400 500 Communication Rounds 40 50 60 70 80 90 Final Cumulative Regret FLDB-OGD (K=5) F…
Figure 5
Figure 5. Figure 5: Final cumulative regret versus local update period [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

64 extracted references · 40 canonical work pages

  1. [1]

    Optimal algorithms for stochastic contextual preference bandits

    Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits. In Proc. NeurIPS, pages 30050–30062, 2021

    2021

  2. [2]

    Efficient and optimal algorithms for contextual dueling bandits under realizability

    Aadirupa Saha and Akshay Krishnamurthy. Efficient and optimal algorithms for contextual dueling bandits under realizability. In Proc. ALT, pages 968–994, 2022

    work page 2022

  3. [3]

    Stochastic contextual dueling bandits under linear stochastic transitivity models

    Viktor Bengs, Aadirupa Saha, and Eyke Hüllermeier. Stochastic contextual dueling bandits under linear stochastic transitivity models. In Proc. ICML, pages 1764–1786, 2022

    2022

  4. [4]

    Feel-good thompson sampling for contextual dueling bandits

    Xuheng Li, Heyang Zhao, and Quanquan Gu. Feel-good thompson sampling for contextual dueling bandits. arXiv:2404.06013, 2024

    arXiv 2024

  5. [5]

    The k-armed dueling bandits problem

    Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, pages 1538–1556, 2012

    2012

  6. [6]

    Prompt optimization with human feedback.arXiv preprint arXiv:2405.17346, 2024

    Xiaoqiang Lin, Zhongxiang Dai, Arun Verma, See-Kiong Ng, Patrick Jaillet, and Bryan Kian Hsiang Low. Prompt optimization with human feedback.arXiv preprint arXiv:2405.17346, 2024

    arXiv 2024

  7. [7]

    Reinforcement learning from human feedback with active queries

    Kaixuan Ji, Jiafan He, and Quanquan Gu. Reinforcement learning from human feedback with active queries. arXiv preprint arXiv:2402.09401, 2024

    arXiv 2024

  8. [8]

    Communication-efficient learning of deep networks from decentralized data

    Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017

    2017

Show all 64 references
  1. [9]

    Federated multi-armed bandits

    Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In Proc. AAAI, 2021

    2021

  2. [10]

    Distributed bandit learning: Near-optimal regret with efficient communication

    Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near-optimal regret with efficient communication. arXiv preprint arXiv:1904.06309, 2019

    1904 arXiv

  3. [11]

    Improved algorithms for linear stochastic bandits

    Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Proc. NeurIPS, pages 2312–2320, 2011

    2011

  4. [12]

    Federated neural bandits

    Zhongxiang Dai, Yao Shu, Arun Verma, Flint Xiaofeng Fan, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated neural bandits. arXiv preprint arXiv:2205.14309, 2022

    2022 arXiv

  5. [13]

    Mm algorithms for generalized bradley-terry models

    David R Hunter. Mm algorithms for generalized bradley-terry models. Annals of Statistics, pages 384–406, 2004

    2004

  6. [14]

    Individual choice behavior: A theoretical analysis

    R Duncan Luce. Individual choice behavior: A theoretical analysis. Courier Corporation, 2005

    2005

  7. [15]

    Provably optimal algorithms for generalized linear contextual bandits

    Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In Proc. ICML, pages 2071–2080, 2017

    2017

  8. [16]

    An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling, 2021

    Qin Ding, Cho-Jui Hsieh, and James Sharpnack. An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling, 2021

    2021

  9. [17]

    Provably optimal algorithms for generalized linear contextual bandits, 2017

    Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits, 2017. 10

    2017

  10. [18]

    Stochastic linear contextual bandits with diverse contexts, 2020

    Weiqiang Wu, Jing Yang, and Cong Shen. Stochastic linear contextual bandits with diverse contexts, 2020

    2020

  11. [19]

    Introduction to online convex optimization

    Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends® in Optimization, 2(3-4):157–325, 2016

    2016

  12. [20]

    Pytorch: An imperative style, high-performance deep learning library, 2019

    Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fan...

    2019

  13. [21]

    Maxwell Harper and Joseph A

    F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4), December 2015

    2015

  14. [22]

    Zhiyong Wang, Jize Xie, Xutong Liu, Shuai Li, and John C. S. Lui. Online clustering of bandits with misspecified user models, 2023

    2023

  15. [23]

    Privacy-preserving communication-efficient federated multi-armed bandits

    Tan Li and Linqi Song. Privacy-preserving communication-efficient federated multi-armed bandits. IEEE Journal on Selected Areas in Communications, 2022

    2022

  16. [24]

    Federated optimization in heterogeneous networks

    Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2:429–450, 2020

    2020

  17. [25]

    Federated multi-armed bandits with personalization

    Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi-armed bandits with personalization. In Proc. AISTATS, pages 2917–2925, 2021

    2021

  18. [26]

    Differentially-private federated linear bandits

    Abhimanyu Dubey and Alex Pentland. Differentially-private federated linear bandits. In Proc. NeurIPS, pages 6003–6014, 2020

    2020

  19. [27]

    Federated linear contextual bandits

    Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. In Proc. NeurIPS, 2021

    2021

  20. [28]

    Asynchronous upper confidence bound algorithms for federated linear bandits

    Chuanhao Li and Hongning Wang. Asynchronous upper confidence bound algorithms for federated linear bandits. In Proc. AISTATS, 2022

    2022

  21. [29]

    Federated bayesian optimization via thompson sampling

    Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated bayesian optimization via thompson sampling. Advances in Neural Information Processing Systems, 33:9687–9699, 2020

    2020

  22. [30]

    Differentially private federated Bayesian optimization with distributed exploration

    Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Differentially private federated Bayesian optimization with distributed exploration. In Proc. NeurIPS, 2021

    2021

  23. [31]

    Communication effi- cient distributed learning for kernelized contextual bandits

    Chuanhao Li, Huazheng Wang, Mengdi Wang, and Hongning Wang. Communication effi- cient distributed learning for kernelized contextual bandits. Advances in Neural Information Processing Systems, 35:19773–19785, 2022

    2022

  24. [32]

    Communication efficient federated learning for generalized linear bandits

    Chuanhao Li and Hongning Wang. Communication efficient federated learning for generalized linear bandits. Advances in Neural Information Processing Systems, 35:38411–38423, 2022

    2022

  25. [33]

    Federated bandit: A gossiping approach

    Zhaowei Zhu, Jingxuan Zhu, Ji Liu, and Yang Liu. Federated bandit: A gossiping approach. Proc. ACM Meas. Anal. Comput. Syst., 5(1):1–29, 2021

    2021

  26. [34]

    SAMBA: A generic framework for secure federated multi-armed bandits

    Radu Ciucanu, Pascal Lafourcade, Gael Marcadet, and Marta Soare. SAMBA: A generic framework for secure federated multi-armed bandits. JAIR, 73:737–765, 2022

    2022

  27. [35]

    Federated linear contextual bandits with heterogeneous clients

    Ethan Blaser, Chuanhao Li, and Hongning Wang. Federated linear contextual bandits with heterogeneous clients. In International Conference on Artificial Intelligence and Statistics , pages 631–639. PMLR, 2024

    2024

  28. [36]

    Federated linear bandits with finite adversarial actions

    Li Fan, Ruida Zhou, Chao Tian, and Cong Shen. Federated linear bandits with finite adversarial actions. Advances in Neural Information Processing Systems, 36, 2024. 11

    2024

  29. [37]

    Federated contextual cascading bandits with asynchronous communication and heterogeneous users

    Hantao Yang, Xutong Liu, Zhiyong Wang, Hong Xie, John CS Lui, Defu Lian, and Enhong Chen. Federated contextual cascading bandits with asynchronous communication and heterogeneous users. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 38, pages 20596–2...

    2024

  30. [38]

    Fairness and privacy guarantees in federated contextual bandits

    Sambhav Solanki, Shweta Jain, and Sujit Gujar. Fairness and privacy guarantees in federated contextual bandits. arXiv preprint arXiv:2402.03531, 2024

    2024 arXiv

  31. [39]

    Federated combinatorial multi- agent multi-armed bandits

    Fares Fourati, Mohamed-Slim Alouini, and Vaneet Aggarwal. Federated combinatorial multi- agent multi-armed bandits. arXiv preprint arXiv:2405.05950, 2024

    2024 arXiv

  32. [40]

    Towards fair and scalable trial assignment in federated bandits: A shapley value approach

    Zibo Wang, Yifei Zhu, Dan Wang, and Zhu Han. Towards fair and scalable trial assignment in federated bandits: A shapley value approach. IEEE Transactions on Big Data, 2024

    2024

  33. [41]

    Federated x-armed bandit

    Wenjie Li, Qifan Song, Jean Honorio, and Guang Lin. Federated x-armed bandit. InProceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 13628–13636, 2024

    2024

  34. [42]

    Incentivized truthful communication for federated bandits

    Zhepei Wei, Chuanhao Li, Tianze Ren, Haifeng Xu, and Hongning Wang. Incentivized truthful communication for federated bandits. arXiv preprint arXiv:2402.04485, 2024

    2024 arXiv

  35. [43]

    Fedconpe: Efficient federated conversational bandits with heterogeneous clients

    Zhuohua Li, Maoli Liu, and John Lui. Fedconpe: Efficient federated conversational bandits with heterogeneous clients. arXiv preprint arXiv:2405.02881, 2024

    2024 arXiv

  36. [44]

    Interactively optimizing information retrieval systems as a dueling bandits problem

    Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems as a dueling bandits problem. In Proc. ICML, pages 1201–1208, 2009

    2009

  37. [45]

    Beat the mean bandit

    Yisong Yue and Thorsten Joachims. Beat the mean bandit. In Proc. ICML, pages 241–248, 2011

    2011

  38. [46]

    Relative confidence sampling for efficient on-line ranker evaluation

    Masrour Zoghi, Shimon A Whiteson, Maarten De Rijke, and Remi Munos. Relative confidence sampling for efficient on-line ranker evaluation. In Proc. WSDM, pages 73–82, 2014

    2014

  39. [47]

    Reducing dueling bandits to cardinal bandits

    Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In Proc. ICML, pages 856–864, 2014

    2014

  40. [48]

    Relative upper confidence bound for the k-armed dueling bandit problem

    Masrour Zoghi, Shimon Whiteson, Remi Munos, and Maarten Rijke. Relative upper confidence bound for the k-armed dueling bandit problem. In Proc. ICML, pages 10–18, 2014

    2014

  41. [49]

    Regret lower bound and optimal algorithm in dueling bandit problem

    Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Proc. COLT, pages 1141–1154, 2015

    2015

  42. [50]

    A relative exponential weighing algorithm for adversarial utility-based dueling bandits

    Pratik Gajane, Tanguy Urvoy, and Fabrice Clérot. A relative exponential weighing algorithm for adversarial utility-based dueling bandits. In Proc. ICML, pages 218–227, 2015

    2015

  43. [51]

    Battle of bandits

    Aadirupa Saha and Aditya Gopalan. Battle of bandits. In Proc. UAI, pages 805–814, 2018

    2018

  44. [52]

    Active ranking with subset-wise preferences

    Aadirupa Saha and Aditya Gopalan. Active ranking with subset-wise preferences. In Proc. AISTATS, pages 3312–3321, 2019

    2019

  45. [53]

    Pac battling bandits in the plackett-luce model

    Aadirupa Saha and Aditya Gopalan. Pac battling bandits in the plackett-luce model. In Proc. ALT, pages 700–737, 2019

    2019

  46. [54]

    Exploiting correlation to achieve faster learning rates in low-rank preference bandits

    Aadirupa Saha and Suprovat Ghoshal. Exploiting correlation to achieve faster learning rates in low-rank preference bandits. In Proc. AISTATS, pages 456–482, 2022

    2022

  47. [55]

    Principled reinforcement learning with human feedback from pairwise or k-wise comparisons

    Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In Proc. ICML, pages 43037–43067, 2023

    2023

  48. [56]

    Variance-aware regret bounds for stochastic contextual dueling bandits

    Qiwei Di, Tao Jin, Yue Wu, Heyang Zhao, Farzad Farnoud, and Quanquan Gu. Variance-aware regret bounds for stochastic contextual dueling bandits. arXiv:2310.00968, 2023

    2023 arXiv

  49. [57]

    Neural dueling bandits

    Arun Verma, Zhongxiang Dai, Xiaoqiang Lin, Patrick Jaillet, and Bryan Kian Hsiang Low. Neural dueling bandits. arXiv preprint arXiv:2407.17112, 2024. 12

    2024 arXiv

  50. [58]

    Clustering of conversational ban- dits for user preference learning and elicitation

    Junda Wu, Canzhe Zhao, Tong Yu, Jingyang Li, and Shuai Li. Clustering of conversational ban- dits for user preference learning and elicitation. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 2129–2139, 2021

    2021

  51. [59]

    Cas- cading bandits for large-scale recommendation problems

    Shi Zong, Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng Wen, and Branislav Kveton. Cas- cading bandits for large-scale recommendation problems. arXiv preprint arXiv:1603.05359, 2016

    2016 arXiv

  52. [60]

    Introduction to online convex optimization, 2023

    Elad Hazan. Introduction to online convex optimization, 2023. 13 A Details of the Vanilla FLDB-GD Algorithm In this section, we provide the detailed descriptions of our vanilla FLDB-GD algorithm (Sec. 3.1). Algorithm 3 FLDB-GD (Agent i) 1: Initialization: Wsync = λ κµ Id×d, θs...

    2023

  53. [61]

    Then we have that Mt ≥ κµVt and that V −1 t ≥ κµM −1 t

    and using mean-value theorem, we get: Gt(θf ′ 1 ) − Gt(θf ′ 2 ) =   tX s=1 ˙µ(θ⊤ ¯f eϕs) eϕs eϕ⊤ s + λI   (θf ′ 1 − θf ′ 2 ) θf is constant (9) Define Mt = hPt s=1 ˙µ(θ⊤ ¯f eϕs) eϕs eϕ⊤ s + λI i , and define Vt = Pt s=1 eϕs eϕ⊤ s + λ κµ I. Then we have that Mt ≥ κµVt and t...

  54. [62]

    bad iterations

    It is easy to verify that Vt−1 ⪰ λ κµ I and hence V −1 t−1 ⪯ κµ λ I. Therefore, we have that eϕt 2 V −1 t−1 ≤ 18 κµ λ eϕt 2 2 ≤ κµ λ . We choose λ such that κµ λ ≤ 1, which ensures that eϕt 2 V −1 t−1 ≤ 1. Our proof here mostly follows from Lemma 11 of [ 11]. To begin with, no...

  55. [63]

    Meanwhile, θt, bθ(t+1), eθ(t) ∈ B 3r with probability at least 1 − δ

  56. [64]

    (33) Summing over s, we have that tX s=1 f fed s (eθt) ≥ tX s=1 f fed s (θt) +   tX s=1 ∇f fed s (θt)⊤   eθt − θt + αt 2 ∥eθt − θt∥2

    Then using the property of α-strongly convex we have f fed s (eθ(t)) ≥ f fed s (θt) + ∇f fed s (θt)⊤ eθ(t) − θt + α 2 ∥eθ(t) − θt∥2. (33) Summing over s, we have that tX s=1 f fed s (eθt) ≥ tX s=1 f fed s (θt) +   tX s=1 ∇f fed s (θt)⊤   eθt − θt + αt 2 ∥eθt − θt∥2. (34) S...

Pith tools

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