Pith. sign in

REVIEW 59 references

Active Human Feedback Collection via Neural Contextual Dueling Bandits

T0 review · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read Neural-ADB claims an O~((d/T)^(1/2)) worst sub-optimality gap for active contextual dueling bandits with non-linear rewards, but the proof relies on a reversed matrix inequality.

arxiv 2504.12016 v2 pith:R6ZQDSCQ submitted 2025-04-16 cs.LG

Arun Verma , Xiaoqiang Lin , Zhongxiang Dai , Daniela Rus , Bryan Kian Hsiang Low This is my paper · ORCID
classification cs.LG
keywords preferencefeedbackhumanneural-adbcollectingcontextualduelingfunction
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

Human preference feedback is expensive. In systems like movie recommendations or aligning chat assistants, a designer wants to ask users to compare a small number of choices rather than exhaustively rate everything. Earlier algorithms that choose which comparisons to ask assumed the hidden quality score, or reward, of each choice is a linear function of its features. This paper replaces that assumption with a neural network, which can represent more complex rewards.

The proposed algorithm, Neural-ADB, works in two steps at each round. It first picks a context, for example a prompt, using a diversity rule adapted from prior work. It then picks two arms, for example two responses, to show the human. The first arm is the current best guess of the network. The second arm is chosen either by the upper-confidence-bound rule or by Thompson sampling, so the algorithm explores while exploiting. The authors state a theorem that the worst gap between the best possible choice and the learned policy shrinks at a rate of roughly one over the square root of the number of comparisons, provided the reward is a bounded non-linear function.

The proof relies on a new matrix concentration lemma. That lemma, Theorem 1, tries to lower-bound the smallest eigenvalue of the accumulated feature covariance matrix. The paper assumes each per-step covariance is bounded above by a matrix Sigma_max, but then uses this upper bound as if it were a lower bound. Only the reverse inequality follows. As a result, the denominator in the main gap bound is not justified, and the central theoretical guarantee is not supported as written. The experiments are synthetic and show Neural-ADB beating several baselines, but they do not repair the proof.

Extended reading notes

Core claim

The worst sub-optimality gap of the policy learned by Neural-ADB with UCB- or TS-based arm selection decreases at rate O~((d/T)^(1/2)) (Theorems 2 and 3). If correct, this means active preference collection with non-linear rewards closes the sub-optimality gap at a sub-linear rate in the number of comparisons T, improving on prior linear-reward active dueling bandits.

Load-bearing premise

Theorem 1 requires a growing lower bound on the minimum eigenvalue of the accumulated Gram matrix, but it assumes only the per-step covariance upper bound Sigma_s <= Sigma_max. From that assumption one can conclude lambda_min(E[V_T]) <= T lambda_min(Sigma_max), not >=; the proof in Appendix A.1 uses the wrong direction. Without an explicit lower bound on the minimum eigenvalue of the design matrix, the denominator G_T in the gap bound has no basis. This premise enters at Theorem 1 and propagates through Lemma 2 into Theorems 2 and 3.

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.

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

The algorithm introduces no new physical or formal entities. The theoretical claim rests on the four assumptions above; the fourth is not merely an assumption but a direction error in the proof.

free parameters (2)
  • nu_T (exploration width) = 1.0
    In all experiments nu_T is fixed to 1.0 rather than the theory-defined value; this constant scales the UCB/TS confidence bonus and directly controls exploration in the reported results.
  • Neural network architecture and training schedule = width 50, 2 hidden layers, retrain every 20 rounds for 50 gradient steps
    The theory requires w >= poly(T,...), but w=50 is used without verifying this condition; the empirical performance depends on these hand-picked values.
assumptions (4)
  • domain assumption Assumption 1: kappa_mu = inf ... mu'(...) > 0 and mu is Lipschitz with constant L_mu.
    Standard dueling-bandit assumption used to build confidence ellipsoids around reward differences.
  • domain assumption The true reward function f lies in the NTK function class with norm bounded by B.
    Needed for the confidence bounds imported from Verma et al. 2025 via Lemma 2, but not stated as an assumption in this paper.
  • domain assumption All pairwise feature differences z are bounded: ||z||_2 <= L.
    Used throughout Theorem 1 and the final gap bound; holds for bounded feature maps but is not proven for the random-feature approximations used in Eq. (3).
  • ad hoc to paper The per-step covariance satisfies Sigma_s <= Sigma_max, and this upper bound is used to lower-bound lambda_min(V_T).
    This is the invalid step in Theorem 1; an upper bound on covariance cannot produce a lower bound on the minimum eigenvalue of the accumulated design matrix.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Active Human Feedback Collection via Neural Contextual Dueling Bandits." pith.science (2026). https://pith.science/paper/R6ZQDSCQ

@misc{pith2026250412016,
  author       = {Pith},
  title        = {Pith review of: Active Human Feedback Collection via Neural Contextual Dueling Bandits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R6ZQDSCQ}},
  note         = {Machine review of arXiv:2504.12016}
}
read the original abstract

Collecting human preference feedback is often expensive, leading recent works to develop principled algorithms to select them more efficiently. However, these works assume that the underlying reward function is linear, an assumption that does not hold in many real-life applications, such as online recommendation and LLM alignment. To address this limitation, we propose Neural-ADB, an algorithm based on the neural contextual dueling bandit framework that provides a principled and practical method for collecting human preference feedback when the underlying latent reward function is non-linear. We theoretically show that when preference feedback follows the Bradley-Terry-Luce model, the worst sub-optimality gap of the policy learned by Neural-ADB decreases at a sub-linear rate as the preference dataset increases. Our experimental results on preference datasets further corroborate the effectiveness of Neural-ADB.

Figures

Figures reproduced from arXiv: 2504.12016 by the authors.

Figure 1
Figure 1. Performance comparison of Neural-ADB against different active dueling bandit algorithms on synthetic functions: Square function (top row) and Sine function (bottom row). (a) Suboptimality Gap (b) MAE (c) Average Regret (d) Suboptimality Gap (e) MAE (f) Average Regret [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Performance of Neural-ADB (UCB) on the Square function, evaluated across varying input dimensions (top row) and numbers of arms (bottom row). (representing human preference feedback) is sampled from a Bernoulli distribution with parameter µ (f(xt,1) − f(xt,2))), where f is either a Square or Sine function.. Reward function estimation. We use a neural network with 2 hidden layers with width 50 to estimate the latent … view at source ↗
Figure 3
Figure 3. Performance of Neural-ADB (TS) on the Square function, evaluated across varying input dimensions (top row) and numbers of arms (bottom row). variants of AE-Borda and APO in which we use a neural network to estimate the latent reward function. They are named AE-Borda (NN) and Neural-ADB (APO) respectively. Experimental results in [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Performance comparison across different input dimensions [PITH_FULL_IMAGE:figures/full_fig_p018_4.png]
Figure 5
Figure 5. Figure 5: Performance comparison across different numbers of arms [PITH_FULL_IMAGE:figures/full_fig_p018_5.png]
Figure 6
Figure 6. Figure 6: We compare performance across different neural network widths (first row) and numbers [PITH_FULL_IMAGE:figures/full_fig_p019_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 45 canonical work pages

  1. [1]

    Improved algorithms for linear stochastic bandits

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

    work page 2011

  2. [2]

    Thompson sampling for contextual bandits with linear payoffs

    Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In Proc. ICML, pages 127--135, 2013

    work page 2013

  3. [3]

    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

    work page 2014

  4. [4]

    Finite-time analysis of the multiarmed bandit problem

    Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, pages 235--256, 2002

    work page 2002

  5. [5]

    Bandits for online calibration: An application to content moderation on social media platforms

    Vashist Avadhanula, Omar Abdul Baki, Hamsa Bastani, Osbert Bastani, Caner Gocmen, Daniel Haimovich, Darren Hwang, Dima Karamshuk, Thomas Leeper, Jiayuan Ma, et al. Bandits for online calibration: An application to content moderation on social media platforms. arXiv:2211.06516, 2022

    arXiv 2022

  6. [6]

    Neural logistic bandits

    Seoungbin Bae and Dabeen Lee. Neural logistic bandits. arXiv:2505.02069, 2025

    arXiv 2025

  7. [7]

    Training a helpful and harmless assistant with reinforcement learning from human feedback

    Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv:2204.05862, 2022

    arXiv 2022

  8. [8]

    Ee-net: Exploitation-exploration neural networks in contextual bandits

    Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Ee-net: Exploitation-exploration neural networks in contextual bandits. In Proc. ICLR, 2022

    work page 2022

Show all 59 references
  1. [9]

    Preference-based online learning with dueling bandits: A survey

    Viktor Bengs, R \'o bert Busa-Fekete, Adil El Mesaoudi-Paul, and Eyke H \"u llermeier. Preference-based online learning with dueling bandits: A survey. Journal of Machine Learning Research, pages 1--108, 2021

    2021

  2. [10]

    Stochastic contextual dueling bandits under linear stochastic transitivity models

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

    2022

  3. [11]

    An empirical evaluation of thompson sampling

    Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Proc. NeurIPS, pages 2249--2257, 2011

    2011

  4. [12]

    Rlhf deciphered: A critical analysis of reinforcement learning from human feedback for llms

    Shreyas Chaudhari, Pranjal Aggarwal, Vishvak Murahari, Tanmay Rajpurohit, Ashwin Kalyan, Karthik Narasimhan, Ameet Deshpande, and Bruno Castro da Silva. Rlhf deciphered: A critical analysis of reinforcement learning from human feedback for llms. arXiv:2404.08555, 2024

    2024 arXiv

  5. [13]

    On kernelized multi-armed bandits

    Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proc. ICML, pages 844--853, 2017

    2017

  6. [14]

    Federated neural bandits

    Zhongxiang Dai, Yao Shu, Arun Verma, Flint Xiaofeng Fan, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated neural bandits. In Proc. ICLR, 2023

    2023

  7. [15]

    Provably sample efficient rlhf via active preference optimization

    Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury. Provably sample efficient rlhf via active preference optimization. arXiv:2402.10500, 2024

    2024 arXiv

  8. [16]

    Contextual bandits with online neural regression

    Rohan Deb, Yikun Ban, Shiliang Zuo, Jingrui He, and Arindam Banerjee. Contextual bandits with online neural regression. In Proc. ICLR, 2024

    2024

  9. [17]

    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

  10. [18]

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

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

    2015

  11. [19]

    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

  12. [20]

    Neural tangent kernel: Convergence and generalization in neural networks

    Arthur Jacot, Franck Gabriel, and Cl \'e ment Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Proc. NeurIPS, pages 8580--8589, 2018

    2018

  13. [21]

    Reinforcement learning from human feedback with active queries

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

    2024 arXiv

  14. [22]

    A fast bandit algorithm for recommendation to users with heterogenous tastes

    Pushmeet Kohli, Mahyar Salek, and Greg Stoddard. A fast bandit algorithm for recommendation to users with heterogenous tastes. In Proc. AAAI, pages 1135--1141, 2013

    2013

  15. [23]

    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

  16. [24]

    Asymptotically efficient adaptive allocation rules

    Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, pages 4--22, 1985

    1985

  17. [25]

    Bandit Algorithms

    Tor Lattimore and Csaba Szepesv\'ari. Bandit Algorithms. Cambridge University Press, 2020

    2020

  18. [26]

    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

  19. [27]

    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

    2024 arXiv

  20. [28]

    Use your instinct: Instruction optimization using neural bandits coupled with transformers

    Xiaoqiang Lin, Zhaoxuan Wu, Zhongxiang Dai, Wenyang Hu, Yao Shu, See-Kiong Ng, Patrick Jaillet, and Bryan Kian Hsiang Low. Use your instinct: Instruction optimization using neural bandits coupled with transformers. arXiv:2310.02905, 2023

    arXiv

  21. [29]

    Prompt optimization with human feedback

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

    2024 arXiv

  22. [30]

    Individual choice behavior: A theoretical analysis

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

    2005

  23. [31]

    Sample efficient reinforcement learning from human feedback via active exploration

    Viraj Mehta, Vikramjeet Das, Ojash Neopane, Yijia Dai, Ilija Bogunovic, Jeff Schneider, and Willie Neiswanger. Sample efficient reinforcement learning from human feedback via active exploration. arXiv:2312.00267, 2023

    2023 arXiv

  24. [32]

    Teaching language models to support answers with verified quotes

    Jacob Menick, Maja Trebacz, Vladimir Mikulik, John Aslanides, Francis Song, Martin Chadwick, Mia Glaese, Susannah Young, Lucy Campbell-Gillingham, Geoffrey Irving, et al. Teaching language models to support answers with verified quotes. arXiv:2203.11147, 2022

    2022 arXiv

  25. [33]

    Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling

    Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. In Proc. ICLR, 2018

    2018

  26. [34]

    Optimal algorithms for stochastic contextual preference bandits

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

    2021

  27. [35]

    Battle of bandits

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

    2018

  28. [36]

    Active ranking with subset-wise preferences

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

    2019

  29. [37]

    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 b

    2019

  30. [38]

    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

    2022

  31. [39]

    Computing parametric ranking models via rank-breaking

    Hossein Azari Soufiani, David Parkes, and Lirong Xia. Computing parametric ranking models via rank-breaking. In Proc. ICML, pages 360--368, 2014

    2014

  32. [40]

    Gaussian process optimization in the bandit setting: No regret and experimental design

    Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. ICML, page 1015–1022, 2010

    2010

  33. [41]

    On the likelihood that one unknown probability exceeds another in view of the evidence of two samples

    William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, pages 285--294, 1933

    1933

  34. [42]

    User-friendly tail bounds for sums of random matrices

    Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, pages 389--434, 2012

    2012

  35. [43]

    Online algorithm for unsupervised sensor selection

    Arun Verma, Manjesh K Hanawal, Csaba Szepesv \'a ri, and Venkatesh Saligrama. Online algorithm for unsupervised sensor selection. In Proc. AISTATS, pages 3168--3176, 2019

    2019

  36. [44]

    Thompson sampling for unsupervised sequential selection

    Arun Verma, Manjesh K Hanawal, and Nandyala Hemachandra. Thompson sampling for unsupervised sequential selection. In Proc. ACML, pages 545--560, 2020 a

    2020

  37. [45]

    Online algorithm for unsupervised sequential selection with contextual information

    Arun Verma, Manjesh K Hanawal, Csaba Szepesv \'a ri, and Venkatesh Saligrama. Online algorithm for unsupervised sequential selection with contextual information. In Proc. NeurIPS, pages 778--788, 2020 b

    2020

  38. [46]

    Neural dueling bandits: Preference-based optimization with human feedback

    Arun Verma, Zhongxiang Dai, Xiaoqiang Lin, Patrick Jaillet, and Bryan Kian Hsiang Low. Neural dueling bandits: Preference-based optimization with human feedback. In Proc. ICLR, 2025

    2025

  39. [47]

    Gaussian Processes for Machine Learning

    Christopher KI Williams and Carl Edward Rasmussen. Gaussian Processes for Machine Learning. MIT press, 2006

    2006

  40. [48]

    Personalized news recommendation: Methods and challenges

    Chuhan Wu, Fangzhao Wu, Yongfeng Huang, and Xing Xie. Personalized news recommendation: Methods and challenges. ACM Transactions on Information Systems, pages 1--50, 2023

    2023

  41. [49]

    Neural contextual bandits with deep representation and shallow exploration

    Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. In Proc. ICLR, 2022

    2022

  42. [50]

    Conversational dueling bandits in generalized linear models

    Shuhua Yang, Hui Yuan, Xiaoying Zhang, Mengdi Wang, Hong Zhang, and Huazheng Wang. Conversational dueling bandits in generalized linear models. In Proc. SIGKDD, pages 3806--3817, 2024

    2024

  43. [51]

    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

  44. [52]

    Beat the mean bandit

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

    2011

  45. [53]

    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

  46. [54]

    Neural Thompson sampling

    Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural Thompson sampling. In Proc. ICLR, 2021

    2021

  47. [55]

    Prompt learning for news recommendation

    Zizhuo Zhang and Bang Wang. Prompt learning for news recommendation. In Proc. SIGIR, pages 227--237, 2023

    2023

  48. [56]

    Neural contextual bandits with UCB -based exploration

    Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB -based exploration. In Proc. ICML, pages 11492--11502, 2020

    2020

  49. [57]

    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

  50. [58]

    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 a

    2014

  51. [59]

    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 b

    2014

Pith tools

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