論文の概要: Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds

• arxiv url: http://arxiv.org/abs/2610.29381v1
• Date: Wed, 21 Oct 2026 08:10:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-23 00:40:06.286299
• Title: Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds
• Title（参考訳）: 雑音観測によるカスケード帯域:アルゴリズムとレグレト境界
• Abstract要約: 位置依存的なコストを発生させるため、注文されたショートリストが$L$のアームから$K$のショートリストを探索するカスケードバンディット構成を提案する。 我々は、アーム単位のスコアに応じてアームをソートすることで最適なショートリストを見つけることができるノイズモデルのサブクラスを同定する。
• 参考スコア（独自算出の注目度）: 3.492181435905197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.
• Abstract（参考訳）: そこで,本研究では,各アームの真の出力に関するノイズフィードバックのみを学習者が観測し,整列したショートリストを$L$のアームから$K$で探索する,新しい確率的カスケーディング・バンディット構成を提案する。 我々は、アーム単位のスコアに応じて最適なショートリストをソートすることで、最適なショートリストを見つけることができるノイズモデルのサブクラスを同定する:そのようなスコアは、チャンネルに偽陽性がないときの選択と順序の両方に存在し、測定コストが無ければ単独で(選択はしないが)注文する。 選択と順序付けの両方のスコアが存在する場合、UCBベースのアルゴリズムに$O((L-K)\log T)$インスタンス依存の後悔を与える。 スコアが存在しないより困難なシナリオでは、厳密な動的プログラムに直接楽観性を組み込む新しいアルゴリズムテンプレートDP-UCBを開発し、$O\big(LK\log T\big)を後悔する。 最後に, 合成および実世界の両方のデータセット上での広範な数値評価とシミュレーションにより, 理論的結果を検証した。

関連論文リスト

• Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback [0.8287206589886881]
  本稿では,ロジスティック・コンテクスト・スレート・バンド問題について考察する。 選択したスレートに対して、ロジスティックモデルにより決定された単一のバイナリ報酬が観測される。 本稿では,Slate-GLM-OFUとSlate-GLM-TSの2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-16T07:19:02Z)
• Rising Rested Bandits: Lower Bounds and Efficient Algorithms [15.390680055166769]
  本論文は、連続マルチアーマッドバンド(MAB)の分野である。 我々は,腕の期待される報酬が単調に非減少性であり,結束する残留包帯の特定の症例について検討した。 我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
  論文  参考訳（メタデータ） (2024-11-06T22:00:46Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Learning to Select and Rank from Choice-Based Feedback: A Simple Nested Approach [10.293894471295205]
  本研究では、動的アソートによる選択に基づくフィードバックから学習する際のランク付けと選択の問題について検討する。 両学習目標に対して,新しい,シンプルなアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-07-13T05:05:30Z)
• Randomized Exploration is Near-Optimal for Tabular MDP [45.16374124699648]
  強化学習におけるThompson Sampling(TS)ライクアルゴリズムにおけるランダム化値関数を用いた探索について検討する。 1)1つのランダムシードを各エピソードで使用し、2)ベルンシュタイン型のノイズの大きさを算出すると、最悪の$widetildeOleft(HsqrtSATright)$リコールがエピソード時間非均質決定プロセスにバインドされることを示します。
  論文  参考訳（メタデータ） (2021-02-19T01:42:50Z)
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
  我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。 まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。 我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
  論文  参考訳（メタデータ） (2021-02-15T19:10:52Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。