論文の概要: On the Computational Tractability of Robust Bandits

• arxiv url: http://arxiv.org/abs/2610.08740v1
• Date: Tue, 06 Oct 2026 17:38:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 02:58:30.153551
• Title: On the Computational Tractability of Robust Bandits
• Title（参考訳）: ロバスト帯域の計算的トラクタビリティについて
• Abstract要約: 学習者に対して $tildeO(sqrtT)$ regret を付与する特別なケースを特定します。 近年,AIアライメント問題を解決するためには,非実現不可能な学習問題に対する効率的な学習者が不可欠であることが示唆されている。
• 参考スコア（独自算出の注目度）: 1.4323566945483497
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning when the environment does not belong to the learner's hypothesis class is typically handled using agnostic learning guarantees. However, for anything beyond supervised learning, agnostic guarantees are difficult to come by. Recently, imprecise bandits (Kosoy, 2025) (later renamed to robust bandits in Appel and Kosoy, 2025) were introduced as another approach to unrealizable learning in the bandits setting and a $Θ(\sqrt{T})$ regret learner was shown for a large class. However, no computational guarantees were provided. In this paper we identify a special case that admits a polynomial-time learner with $\tilde{O}(\sqrt{T})$ regret. We also show that several small generalizations of this special case are NP-hard thus indicating that the special case is at the boundary of what is tractable. It has been recently suggested (Kosoy, 2018) that computationally efficient learners for unrealizable learning problems are crucial for solving the AI alignment problem. This work is a small step in that direction.
• Abstract（参考訳）: 環境が学習者の仮説クラスに属さない場合の学習は、通常、不可知的な学習保証を用いて扱われる。 しかし、教師付き学習以外には、保証を無視することは困難である。 近年では、不正確な盗賊(後にアデルとコソイの堅固な盗賊に改名された2025年)が、盗賊設定における非実現不可能な学習への別のアプローチとして紹介され、大きなクラスに「後悔の学習者」という$$$$(\sqrt{T}」が提示された。 しかし、計算上の保証は提供されなかった。 本稿では,多項式時間学習者に対して$\tilde{O}(\sqrt{T})$ regretを許容する特別なケースを特定する。 また、この特殊ケースのいくつかの小さな一般化がNPハードであることを示し、特別ケースがトラクタブルの境界にあることを示す。 最近(Kosoy, 2018)では、非実現不可能な学習問題に対する計算効率のよい学習者がAIアライメント問題の解決に不可欠であることが示唆されている。 この仕事はその方向への小さな一歩だ。

関連論文リスト

• Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary [13.08870048693199]
  我々は, 1 つのアルゴリズムが, 難解な敵に対して 1 ドルごとに$widetildemathcalO(sqrt(S+1)KT)$ expected regret を達成することを示す。 提案アルゴリズムは,固定共有学習者と,局所的な改善を探索するダイアディック・インターバルを併用する。
  論文  参考訳（メタデータ） (2026-09-11T21:23:20Z)
• On the Hardness of Bandit Learning [21.32087711586654]
  ベストアーム識別としても知られるバンディット学習の課題について検討する。 我々は、分類のためのPACフレームワークと同様に、包帯学習可能性の一般的な理論を模索する。
  論文  参考訳（メタデータ） (2025-06-17T17:35:25Z)
• Probably Approximately Precision and Recall Learning [60.00180898830079]
  機械学習における重要な課題は、一方的なフィードバックの頻度である。 本稿では,確率的近似(PAC)フレームワークを導入し,各入力をラベルの集合にマッピングする仮説を定めている。 我々は、正のデータのみから学習する新しいアルゴリズムを開発し、実現可能な場合において最適なサンプル複雑性を実現する。
  論文  参考訳（メタデータ） (2024-11-20T04:21:07Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
  バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。 我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-16T12:11:09Z)
• Agnostic Multi-Robust Learning Using ERM [19.313739782029185]
  頑健な学習における根本的な問題は非対称性である: 学習者は指数関数的に多くの摂動の全てを正しく分類する必要がある。 これとは対照的に、攻撃者は1つの摂動を成功させる必要がある。 本稿では,新しいマルチグループ設定を導入し,新しいマルチロバスト学習問題を提案する。
  論文  参考訳（メタデータ） (2023-03-15T21:30:14Z)
• Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization [39.51923275855131]
  本研究では,テスト時間における逆例に頑健な予測器の学習問題に対して,最小限の最適学習器を提案する。 特に、強い否定的な意味で、モンタッサー、ハネケ、スレブロによって提案された頑健な学習者の亜最適性を示す。
  論文  参考訳（メタデータ） (2022-09-15T15:32:42Z)
• There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning for Mazes [64.05903267230467]
  相互理解性は,強化学習システムにおける信頼性に不可欠なビルディングブロックである。 場合によっては、最適性を保ちつつ、政策の解釈可能性を達成することができることを示す。
  論文  参考訳（メタデータ） (2022-06-09T04:23:26Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39:57Z)
• Semi-verified PAC Learning from the Crowd [7.594050968868919]
  本研究では,クラウドソース型PAC学習におけるしきい値関数の問題点について検討する。 本稿では,Charikar等の半検証モデルを用いて,PACが基礎となる仮説クラスを大量のラベルクエリで学習可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-13T20:05:16Z)

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

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