Newest papers

Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds

Yashaswini Kaluguri, Nikhil Karamchandani · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.29381 · cited by 0 works (OpenAlex) · open-access PDF

Vietnamese

Chúng tôi đề xuất một thiết lập kẻ cướp thuần túy thuần túy mới, nơi điều tra một danh sách ngắn được sắp xếp $K$ từ các cánh tay $L$ gây ra chi phí phụ thuộc vào vị trí, và người học chỉ quan sát phản hồi ồn ào liên quan đến sản lượng thực của mỗi cánh tay. Chúng tôi xác định một tiểu lớp của các mô hình tiếng ồn mà danh sách ngắn tối ưu có thể được tìm thấy bằng cách sắp xếp các cánh tay theo điểm số mỗi cánh tay: một điểm số như vậy tồn tại cho cả việc lựa chọn và đặt hàng khi kênh không có dương tính giả, và cho việc đặt hàng một mình (nhưng không lựa chọn) khi các phép đo là miễn phí; tuy nhiên, nói chung, không có lựa chọn cũng như đặt hàng có thể tách rời khi tiếng ồn và chi phí là cả hai hiện diện. Đối với trường hợp cả hai

Machine translation (Meta M2M100); the English original follows.

Abstract

We propose a novel stochastic cascading bandit setup where probing an ordered shortlist of $K$ out of $L$ arms incurs position-dependent costs, and the learner observes only noisy feedback regarding each arm's true output. We identify a sub-class of noise models for which the optimal shortlist can be found by sorting arms according to a per-arm score: such a score exists for both selection and ordering when the channel has no false positives, and for ordering alone (but not selection) when measurements are costless; however in general neither selection nor ordering is separable once noise and cost are both present. For the case where both selection and ordering scores exist, we provide a UCB-based algorithm with $O((L-K)\log T)$ instance-dependent regret over a time horizon $T$, which matches an algorithm-agnostic lower bound (up to constant factors). For the more challenging scenario where scores don't exist, we develop a new algorithmic template, DP-UCB, that embeds optimism directly inside an exact dynamic program, yielding $O\big(LK\log T\big)$ regret. Finally, we validate our theoretical results through extensive numerical evaluations and simulations over both synthetic and real-world datasets.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Regret, Algorithm, Selection (genetic algorithm), Noise (video), Sorting, Upper and lower bounds

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange